Sum#2157
Roman's parents gave him an undirected, connected, weighted graph with vertices and n - 1 edges. Roman wants to find the total length of all paths between every pair of vertices in the graph. The length of a path is defined as the sum of the weights of the edges it includes. Since the path from vertex to vertex is the same as the path from to , Roman treats them as a single path and does not distinguish between them.
The first line contains an integer n~(2 \le n \le 10^5) — the number of vertices in the graph.
Each of the next n - 1 lines describes an edge and contains three integers: the numbers of the two vertices connected by the edge (vertices are numbered from to ), and the weight of the edge.
Print the total length of all distinct paths between all pairs of vertices, modulo 10^9.
Example 1
Example 2