Problem Description

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

You will visit each node in increasing order of its label.

Traversing edges in the tree costs money. For the $i$-th edge, there is a single-use ticket (can only be used once) with price $c_{i1}$, and a multi-use ticket (can be used an unlimited number of times) with price $c_{i2}$. During your trip, you may traverse an edge multiple times, so a multi-use ticket can sometimes be more cost-effective.

Please find the minimum total cost required to visit from $1$ to $n$.

Input Format

• The first line: a positive integer $n$.

• The next $n-1$ lines describe the $n-1$ edges: four positive integers $a_i, b_i, c_{i1}, c_{i2}$, meaning there is an edge connecting $a_i$ and $b_i$ whose single-use ticket costs $c_{i1}$ and multi-use ticket costs $c_{i2}$.

Output Format

Output one line with one positive integer: your answer.

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

10

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

16

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

11

Hint

Sample #1 Explanation

• $1\to 2$: multi-use ticket, cost $5$.
• $2\to 1\to 3$: $2\to 1$ uses the previously bought multi-use ticket, no cost; $1\to 3$ single-use ticket, cost $2$.
• $3\to 1\to 2\to 4$: $3\to 1$ single-use ticket, cost $2$; $1\to 2$ uses the previously bought multi-use ticket, no cost; $2\to 4$ single-use ticket, cost $1$.
• Total cost is $5+2+2+1=10$.

Constraints

This problem uses bundled testdata.

• For $20 pts$ of the testdata, $2\leq n\leq 2000$.

• For another $25 pts$ of the testdata, each town is directly connected to at most two other towns.

• For all testdata, $2\leq n\leq 2\times10^5$, $1\leq a_i, b_i\leq n$, $1\leq c_{i1}\leq c_{i2}\leq 10^5$.

Notes

Translated from COCI2019-2020 CONTEST #5 T4 Putovanje.

Translated by ChatGPT 5