## Paths in a tree

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.

## Comments