Problems
Sum
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.
\InputFile
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.
\OutputFile
Print the sum of all the paths’ lengths in the given graph modulo $10^9$.
\includegraphics{https://static.e-olymp.com/content/1c/1c9962225b484b4be775b21ea4f0cae761cb1c5a.gif}
Input example #1
3 1 2 1 1 3 3
Output example #1
8
Input example #2
6 1 2 5 1 3 1 2 4 2 2 5 4 2 6 3
Output example #2
90
Example description: An explanation to the example: All the paths are 1->2, 1->3, 2->1->3 and their lengths’ sum is 1+3+4=8.