题目2--无根树

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给一棵树,取名为scf0920树,是一棵普通的无根树。假设它有n个节点,节点编号从1到n,定义d(i,j)为i节点到j节点的最短距离,求所有的d(i,j)(1 <= i < j <= n)的和,并对10^9+7取余。

Input

第一行包含一个正整数n(n <= 100000),表示节点个数。
后面(n-1)行,每行前两个整数(u,v)表示树的边,然后一个整数w表示边的长度。
(1 <= u,v <= n, 1 <= w <= 10^4)。

Output

 每行一个整数,表示对10^9+7取余后的值

Sample Input

4
1 2 1
3 2 2
4 2 3

Sample Output

18

Hint

 

Source