Sum of Maximum Weights on Tree Paths

You are given a network of computers connected in a tree structure. Each computer is represented as a node, and there is exactly one path between any two computers. Each connection (edge) has a weight representing the time required to transfer data between the two computers it connects.

For every node (except the root, which is node 1), determine the maximum edge weight encountered along the path from the root to that node. Then, compute the sum of these maximum weights for all nodes other than the root.

For example, consider a network with 5 computers and the following connections:

• Edge between 1 and 2 with weight 3,
• Edge between 1 and 3 with weight 2,
• Edge between 2 and 4 with weight 4,
• Edge between 2 and 5 with weight 1.

The maximum weights for nodes 2, 3, 4 and 5 are 3, 2, 4, and 3 respectively, so the output is 12.

The relationship can be mathematically described as follows: [ S = \sum_{i=2}^{n} \max_{e \in P(i)}w(e), ] where (P(i)) is the set of edges on the path from node 1 to node i, and (w(e)) is the weight of edge (e).

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) ((2 \le n \le 10^5)), representing the number of computers (nodes) in the tree. Each of the next (n-1) lines contains three space-separated integers (u), (v), and (w), describing an edge between node (u) and node (v) with weight (w).

outputFormat

Output a single integer to standard output (stdout): the sum of the maximum weights on the unique paths from the root (node 1) to every other node in the network.## sample

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

12