Problem Description

You are given a tree with $n$ nodes, numbered from $1$ to $n$.

You will visit each node in ascending order of their numbers.

Traveling along the edges of the tree incurs costs. The $i$-th edge has a one-way ticket (usable only once) price of $c_{i1}$ and a multiple-use ticket (usable infinitely) price of $c_{i2}$. Since you may traverse an edge multiple times during your journey, the multiple-use ticket can sometimes be more economical.

Calculate the minimum cost required to travel from node $1$ to node $n$.

Input Format

• The first line: a positive integer $n$.
• The next $n-1$ lines describe the $n-1$ edges: each line contains four positive integers $a_i, b_i, c_{i1}, c_{i2}$, indicating an edge connecting nodes $a_i$ and $b_i$ with a one-way ticket price of $c_{i1}$ and a multiple-use ticket price of $c_{i2}$.

Output Format

A single line containing a positive integer: your answer.

Sample Input and Output

Input Sample #1

4
1 2 3 5
1 3 2 4
2 4 1 3

Output Sample #1

10

Input Sample #2

4
1 4 5 5
3 4 4 7
2 4 2 6

Output Sample #2

16

Input Sample #3

5
1 2 2 3
1 3 2 3
1 4 2 3
1 5 2 3

Output Sample #3

11

Notes

Explanation of Sample #1

• $1 \to 2$: Multiple-use ticket, cost $5$.
• $2 \to 1 \to 3$: $2 \to 1$ uses the purchased multiple-use ticket, no additional cost; $1 \to 3$ one-way ticket, cost $2$.
• $3 \to 1 \to 2 \to 4$: $3 \to 1$ one-way ticket, cost $2$; $1 \to 2$ uses the purchased multiple-use ticket, no additional cost; $2 \to 4$ one-way ticket, cost $1$.
• Total cost: $5 + 2 + 2 + 1 = 10$.

Data Range

This problem is grouped testing.

• For $20$ points: $2 \leq n \leq 2000$.
• For another $25$ points: Each town is directly connected to at most two other towns.
• For all data: $2 \leq n \leq 200000$, $1 \leq a_i, b_i \leq n$, $1 \leq c_{i1} \leq c_{i2} \leq 100000$.

Notes

This problem is translated from COCI2019-2020 CONTEST #5 T4 Putovanje.

见题面 Input 部分

见题面 Output 部分