Minimum Added Weight Sum for Complete Graph

You are given a tree with N nodes and N-1 edges. Each edge in the tree has an integer weight. Your task is to add a set of edges (with integer weights) such that the resulting graph becomes a complete graph (i.e. every pair of distinct vertices is connected by an edge) and the unique minimum spanning tree (MST) of the complete graph is exactly the given tree.

For every pair of vertices u and v that are not directly connected by a tree edge, you need to add an edge with weight w = d(u, v) + 1, where d(u, v) is defined as the maximum weight among the edges on the unique path between u and v in the tree. This assignment guarantees that if any extra edge creates a cycle with the tree, its weight is strictly greater than the maximum edge in that cycle, thus ensuring that the given tree remains the unique MST.

Your goal is to compute the minimum possible sum of the weights of all newly added edges.

Note: Both the weights on the given tree and the weights assigned to the new edges must be integers.

The formula for the weight assigned to an extra edge between u and v is given in \( \LaTeX \) as:

[ w(u,v) = \max_{e \in P(u,v)}{w_e} + 1 ]

where \(P(u,v)\) is the unique path between vertices \(u\) and \(v\) in the tree and \(w_e\) is the weight of edge \(e\) in that path.

inputFormat

The first line contains an integer N (\(2 \leq N \leq 10^5\)), the number of nodes in the tree.

Each of the following N-1 lines contains three space-separated integers: u, v and w (\(1 \leq u,v \leq N\), \(1 \leq w \leq 10^9\)), which denote an edge between nodes u and v with weight w.

outputFormat

Output a single integer, which is the minimum total weight of all the added edges such that the complete graph satisfies the given conditions.

sample

2
1 2 5

0