Synchronized Terminal Activation

A circuit board is composed of several components (nodes) numbered 1,2,3, … . These nodes are connected by non‐intersecting wires so that between any two nodes there is exactly one path (i.e. the board forms a tree). One special node, called the exciter, is activated to produce an excitation current, which is sent along each connected wire. When a node (other than the exciter) receives the excitation current, it immediately forwards the current to all of its adjacent nodes that have not yet received the current. Some nodes, after receiving the current, do not forward it further – these are called terminal nodes.

The current travels along each wire (edge) with a given transmission time. More precisely, every edge e has an initial travel time t_e (a positive integer) that the current requires to pass through it; the forwarding at a node is instantaneous. For the board to work correctly, the excitation current must reach every terminal node simultaneously. However, the board as‐built might not satisfy this time synchronization. To fix the problem, you have a gadget: each time you use it on an edge, you can increase that edge’s travel time by exactly one unit. The gadget may be used arbitrarily many times (each use adds one to some edge’s transmission time).

Assume the exciter is located at node 1. Since the board is a tree, the arrival time at any node is uniquely determined as the sum of the original travel times on the path from node 1 to that node plus any extra delay you introduce. Let d(u) denote the original distance (sum of t_e's) from node 1 to node u. Then, for any terminal node l (which is a leaf in the tree except possibly node 1), its final arrival time will be d(l) + δ(l) where δ(l) is the total extra delay (made by your gadget uses on edges on the unique path from 1 to l). To synchronize the system, we want all terminal nodes to have the same final arrival time T (which must be at least max{ d(l) } over all terminal nodes).

Your task is to determine the minimum total number of gadget uses required such that, by increasing some edge travel times (possibly more than once per edge), every terminal node will receive the excitation current at the same time T (where T = max{ d(l) } for the terminal nodes with the longest path). Note that if an edge is used on the common part of the paths for multiple terminal nodes, a delay added on that edge counts for all terminal nodes in its subtree.

Hint (Solution Outline): Root the tree at node 1 and compute for every node u its original distance d(u). Define F(u) as the maximum original distance (i.e. from node 1) in the subtree of u. Then the desired final time is T = F(1). One may prove that an optimal strategy is to add delays on each edge from a parent u to a child v with an extra delay of T - F(v). In this way, for every terminal node l (which is a leaf in the tree) the total added delay will be exactly

\(\sum_{e\in path(1,l)} (T - F(child)) = T - d(l)\).

Your answer is the sum over all edges of the delay you add, i.e.:

\(\text{Answer} = \sum_{(u,v)} \Bigl(T - F(v)\Bigr)\),

where the sum is taken over every edge directed from a parent u to its child v when the tree is rooted at node 1.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), the number of nodes.

Each of the following n − 1 lines contains three integers u, v and t (1 ≤ u,v ≤ n, 1 ≤ t ≤ 10⁴), which describe a wire connecting nodes u and v with initial transmission time t.

It is guaranteed that the given graph is a tree. The exciter is located at node 1.

outputFormat

Output a single integer, which is the minimum number of gadget uses needed to make the excitation current arrive at all terminal (leaf) nodes simultaneously.

sample

3
1 2 3
1 3 5

2