Synchronizing Fireworks Detonation

During a fireworks display, it is crucial for safety and spectacle that all the fireworks detonate at the same time. The fireworks are connected to a single switch by fuses in a tree structure: the root is the switch and the leaves are the fireworks. When the switch is triggered at time \(0\), sparks travel along the fuses (which burn at a fixed speed), and when a spark reaches a branching point it spreads to all connected fuses.

In the original layout, each fuse has an assigned length, so the explosion time of a firework is the sum of the lengths along the path from the switch to that firework. Unfortunately, the fireworks might not explode simultaneously. To fix this, you are allowed to change the lengths of some fuses. Changing the length of a fuse costs an amount equal to the absolute difference between its new and original lengths. Note that the fuse length can be reduced to \(0\) (while maintaining connectivity).

Your task is to adjust the fuses so that all fireworks detonate at the same moment, and to do so with a minimal total cost. It can be shown that the optimal minimum cost is equal to \(\max_{\text{leaf}} d - \min_{\text{leaf}} d\), where \(d\) is the original explosion time (the sum of fuse lengths from the switch) of a firework (a leaf in the tree).

Input/Output Details: The tree is given as an undirected graph with \(n\) nodes. Node \(1\) is the switch. Each of the following \(n-1\) lines contains three integers \(u\), \(v\) and \(w\) representing an edge between nodes \(u\) and \(v\) with fuse length \(w\). For a tree with only one node (the switch), consider the answer as \(0\).

Your program should compute the minimal total cost required to adjust the fuses so that all fireworks (all leaves except the root, unless the tree consists solely of the root) detonate simultaneously.

Note: If there is only one firework or no firework at all, no adjustment is needed, and the answer is 0.

inputFormat

The first line contains an integer \(n\) (where \(1 \le n \le 10^5\)), the number of nodes in the tree.

If \(n \ge 2\), then each of the next \(n-1\) lines contains three integers \(u\), \(v\) and \(w\) (\(1 \le u,v \le n\), \(0 \le w \le 10^9\)) representing an edge between nodes \(u\) and \(v\) with fuse length \(w\). Node \(1\) is the switch. The tree is connected and has no cycles.

outputFormat

Output a single integer: the minimal total cost required to adjust the fuse lengths so that all fireworks explode simultaneously.

sample

1

0