It's Valentine's day in Mackenzie City, which means Alice and Bob are going on a date frenzy!

There are ~N~ date locations around Mackenzie City, labelled ~1~ to ~N~. The couple wants to visit all the date locations in succession, going from date location ~1~ to ~2~, ~2~ to ~3~ and so on.

Starting at date location ~1~ and ending at location ~N~, they will travel using the network of exactly ~N-1~ bi-directional bus routes connecting the date locations, such that it is possible to take some sequence of buses from any date location to another.

Each bus route has a single-use fare ~f_o~ which needs to be re-purchased every time the couple travels along the route. Each bus route also has a multi-use fare ~f_m~ which can be purchased once, and all future travel on the route is free.

Since the couple would like to spend their money at the date locations rather than transiting, what is the minimum price they must pay for transit? Remember, it's two people!

Constraints

~2 \le N \le 2 \times 10^5~

~1 \le f_o \le f_m \le 10^5~

Input Specification

The first line of input will contain ~N~.

The next ~N-1~ lines will contain ~4~ space-separated integers ~u, v, f_o, f_m~ representing a bi-directional bus route connecting date locations ~u~ and ~v~ with single-use fare ~f_o~ and multi-use fare ~f_m~.

Output Specification

Output the minimum price Alice and Bob must pay for transit to visit all ~N~ date locations in succession.

Sample Input

3
1 3 3 5
3 2 2 3

Sample Output

12

Explanation of Sample Input 1

The couple can buy two ~$3~ single-use fares for the bus route connecting date locations ~1~ and ~3~ and two ~$3~ multi-use fares for the line connecting bus routes ~3~ and ~2~ for a total cost of ~$12~.