## Paths in a tree

Points: 1
Time limit: 2.0s
Memory limit: 512M

Authors:
Problem type

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.