Tree Ticket Optimization

You are given a tree with \( n \) nodes numbered from \(1\) to \( n \). You must visit all the nodes in increasing order, i.e. you start at node \(1\), then visit node \(2\), node \(3\), and so on until node \( n \).

When traversing an edge in the tree, you have to pay a fee. The \( i\)-th edge has two ticket options:

• A single-use ticket costing \( c_{i1} \) (it can only be used for one passage).
• A multi-use ticket costing \( c_{i2} \) (it can be used an unlimited number of times).

Note that on your journey between consecutive nodes (i.e. from node \( i \) to node \( i+1 \)) you will take the unique simple path in the tree. An edge might be traversed multiple times across these consecutive trips. For each edge, if it is traversed \( k \) times, you may either pay \( k \times c_{i1} \) using single‐use tickets or buy a multi‐use ticket for \( c_{i2} \) (and then pay nothing for additional passages). Your task is to compute the minimum total cost needed to travel from node \(1\) to node \( n \) following this order.

The answer is computed as the sum over all edges of \( \min(k \times c_{i1},\; c_{i2}) \) where \( k \) is the number of times that edge is used in the journey. For an edge, if you remove it from the tree, the tree splits into two connected components. When the tree is traversed in the natural order \(1,2,\ldots,n\), let \( b[i] \) be a boolean indicating whether vertex \( i \) lies in the component not containing node \(1\) (which is the unique such component because the journey starts at \(1\)). Then the number of times that the edge is used equals \[ k = \sum_{i=1}^{n-1} \Bigl|b[i+1] - b[i]\Bigr|. \] All formulas are presented in \(\LaTeX\) format.

inputFormat

The first line contains an integer \( n \) (the number of nodes). Each of the following \( n-1 \) lines contains four integers \( u\), \( v \), \( c_{1} \) and \( c_{2} \) describing an edge that connects node \( u \) and node \( v \) with single‐use cost \( c_{1} \) and multi‐use cost \( c_{2} \) respectively.

outputFormat

Output a single integer, the minimum total cost to travel from node \(1\) to node \( n \) while visiting every node in increasing order.

sample

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

6