$1$

$1$

$.$

$$Ada and hackathons

Ada is planning to participate in N hackathons, numbered from

$1$

$$to N

$,$

$$scheduled in N different cities. The ith hackathon happens in city i

$.$

$$Each hackathon j

$($

$>$

$1$

$)$

$$has a prerequisite: one should have participated in all hackathons indexed i

$<$

$$j before participating in the hackathon j

$.$

$$For example, if she wants to participate in hackathon

$4$

$,$

$$she should have already participated in hackathons

$1$

$,$

$2$

$,$

$$and

$3$

$.$

The N cities are connected by N

$-$

$1$

$$bidirectional bus routes so that each city is reachable from the others by using one or more of these buses. The ticketing system for these bus routes is as follows: for each route, she can buy a single trip ticket for T

$\_$

$\{$

i

$\}$

$$coins or a season pass for S

$\_$

$\{$

i

$\}$

$$coins$.$ The single

$-$

trip ticket can be used only once, while the season ticket can be used any number of times for that bidirectional bus route.

Ada is currently at city

$1$

$.$

$$She has already planned her trip and the tickets she would buy so that she can participate in all hackathons by spending the minimum amount on bus tickets. Can you find this minimum cost?

Input Format

The first line contains the number N

$.$

The next N

$-$

$1$

$$lines describe the bus routes. Each line contains

$4$

$$integers A

$\_$

$\{$

i

$\}$

$,$

$$B

$\_$

$\{$

j

$\}$

$,$

$$T

$\_$

$\{$

i

$\}$

$,$

$$S

$\_$

$\{$

j

$\}$

$$representing a bus route between city A

$,$

$$and city B

$\_$

$\{$

i

$\}$

$$with the single trip ticket costing T

$\_$

$\{$

i

$\}$

$$coins and the season pass costing S

$\_$

$\{$

i

$\}$

$$coins$.$

Constraints

$1$

$<$

$=$

$$N

$<$

$=$

$2$

Theta

$*$

Theta

$1$

$<$

$=$

$$A

$\_$

$\{$

i

$\}$

$<$

$=$

$$N

$1$

$<$

$=$

$$B

$\_$

$\{$

i

$\}$

$<$

$=$

$$N

$1$

$<$

$=$

$$T

$<$

$=$

$1$

$$e

$6$

$1$

$<$

$=$

$$S

$\_$

$\{$

j

$\}$

$<$

$=$

$1$

e

$6$

Output Format

Print a single integer which is the minimum amount Ada would have to spend to participate in all hackathons assuming she is already in city

$1$

$.$

Sample Input

$4$

$1$

$2$

$3$

$5$

$1$

$3$

$2$

$4$

$2$

$4$

$1$

$3$

Sample Output

$1$

$0$

write code in c$++$