Putovanje

Time limit1sMemory limit512 MB

Summary

On a tree, visit towns 1 through N in order; each edge costs C1 per traversal or C2 once, so minimize total ticket cost.

Level: Medium7 of 10
Topics: Tree, Greedy, DFS, Implementation
Solved: No attempts yet

Problem

Little Fabijan loves bars and travels. He wishes to drink coffee in each of the N towns in his country, conveniently numbered from 1 to N. The towns are connected by (N − 1) bidirectional roads such that every town is reachable from any other town by traversing some of the roads. Fabijan decided to drink coffee in every town in order from town 1 to town N. Therefore, he starts from town 1 (where he drinks his first coffee) and travels to town 2 for his next cup of coffee. During that travel he might pass through a number of different towns, but he will not make a coffee stop in those towns. After drinking coffee in town 2, he will proceed to travel to town 3, and so on until he finally reaches town N, where he will drink his last coffee.

In order to traverse a certain road, he needs to have a valid ticket. The i-th road can be traversed if you have either a single-pass ticket, which costs Ci1 euros, or a multi-pass ticket, which costs Ci2 euros. For each road, Fabijan can decide to buy a single-pass ticket each time he needs to traverse that road, or he might opt to buy a multi-pass ticket once.

Write a program that computes the smallest number of euros Fabijan needs to spend on tickets in order to successfully complete his travels.

Input

The first line contains an integer N (2 ≤ N ≤ 200 000).

In the i-th of the next (N − 1) lines there are four integers Ai, Bi, Ci1, Ci2 (1 ≤ Ai, Bi ≤ N, 1 ≤ Ci1 ≤ Ci2 ≤ 100 000), which represent that towns Ai and Bi are connected by a road with ticket prices Ci1 and Ci2.

Output

In a single line output the smallest cost of travel.

Examples3

Example 1
Input
```
4
1 2 3 5
1 3 2 4
2 4 1 3
```
Expected output
```
10
```
Example 2
Input
```
4
1 4 5 5
3 4 4 7
2 4 2 6
```
Expected output
```
16
```
Example 3
Input
```
5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3
```
Expected output
```
11
```