Jungol

한컴이는 정올국으로 여행을 떠났다.

정올국은 N개의 도시를 N-1개의 도로가 연결하는 형태이며, 어느 두 임의의 도시도 도로만을 사용해 이동할 수 있다.

한컴이는 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시를 순서대로 이동한 다음 N번 도시에서 비행기를 타고 귀국할 예정이다. 이때 이동하는 도중 중간에 다른 도시에 도착해도 목적지가 아니라면 무시하고 계속 움직일 것이다.

정올국의 각 도로는 두 가지의 요금제가 있다. 첫 번째는 한번 도로를 사용할 때마다 C_{i1}원씩 청구되는 형태이고, 두 번째는 C_{i2}원을 청구한 뒤 차후 무제한으로 도로를 사용하는 형태이다.

한컴이의 여행에 필요한 요금의 최소값을 구하시오.

입력

첫 줄에 도시의 개수 N이 주어진다. (2 ≤ N ≤ 200\ 000)

그 다음 줄부터 N-1줄에 걸쳐 각 도로에 대한 정보 A_i\ , \ B_i\ , \ C_{i1}\ , \ C_{i2}가 주어진다. 이는 i번째 도로가 A_i와 B_i번 도시를 이으며, 각 요금제의 가격은 C_{i1}원과 C_{i2}임을 의미한다.

(1 ≤ A_i, B_i ≤ N, 1 ≤ C_{i1} ≤ C_{i2} ≤ 100\ 000)

출력

한컴이의 여행에 필요한 요금의 최소값을 한 줄에 출력하시오,

부분문제

번호	점수	조건
#1	20점	2<=N<=2000
#2	25점	각 도시는 최대 2개의 다른 도시와 도로로 직접적으로 연결되어 있다.
#3	55점	추가 제한 없음

예제1

예제2

출처

COCI 2019/2020 Contest #5

여행 1초 512MB