Sum

Roman’s parents gave him an undirected connected weighted graph with $n$ vertices and $n–1$ edges. Roman wants to know the sum of all the paths’ lengths in this graph. Let’s consider the path’s length as the sum of all the edges that lie on this path. Roman said that the path from $u$ to $v$ is the same as from $v$ to $u$, so he doesn’t distinguish them.

Input

The first line contains the single integer number $n(2\le n\le 10^5)$ — the number of vertices in the graph. It is followed by $n–1$ lines containing the description of the edges. Every line of description consists of three integers: the vertices connected by the edge (labeled from $1$ to $n$) and the edge’s weight.

Output

Print the sum of all the paths’ lengths in the given graph modulo $10^9$.

Examples