Definition: a tree is an undirected graph in which any two vertices are connected by exactly one path.

You are given a tree of \(N\) vertices. Each edge within this tree has some associated weight assigned to it. You are tasked to find the sum of: the cost for all paths within the tree. In other words, for every ordered pair of vertices within the tree, say vertex \(u\) and \(v\), sum the cost of the path from \(u\) to \(v\).

The cost of a path is denoted by the sum of the weights along each edge within the path. As mentioned above, the path from vertex 1 to 2 is the equivalent to 2 to 1 and thus is not considered again.

Input specification

The first line contains \(N\), the number of vertices in the tree.

\(N - 1\) lines follow of the form: u v w, each line denotes that there is an undirected edge from vertex \(u\) to vertex \(v\) with weight \(w\). Constraints:

• \(1 \leq N \leq 10^5\)
• \(1 \leq u, v \leq N\)
• \(-10^9 \leq w \leq 10^9\)

The input is guaranteed to be a tree.

Output specification

Print a single integer describing the answer.

Example input

3
1 2 2
2 3 2

Example output

8

Example analysis

The example looks like: \(1 - 2 - 3\). The valid paths are \(1 \rightarrow 2\) with a cost of 2, \(2 \rightarrow 3\) with a cost of 2 and \(1 \rightarrow 3\) (\(1 \rightarrow 2 \rightarrow 3\)) with a cost of 4. Add them all up and you get 8.