Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3840
Nuclear Power Plant

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are N (1 ≤ N ≤ 105) cities on land, and there are N - 1 wires connecting the cities. Therefore, each city can transmit electricity to all other cities by these wires.

Dark_Sun made a decision to build a nuclear power plant to supply electricity for all the cities. The nuclear power plant can be built in any city, but the cost for the electricity transmission is very strange. Let the weight of wire which connects city u and city v is E(u, v) (|E(u, v)| < 109). If the power plant is built in city x, the cost for electricity transmission from city x to city y is D(x, y) = (E(x, s1) + E(s1, s2) + ... + E(sp, y))k, where {x, s1, s2, ..., sp, y} is the path from x to y. Because of the bug of the computer, the total cost for building a nuclear power plant in city x is Σ(D(x, i)) mod 100000007 (0 ≤ i < N, ix), and the total cost is obviously not a negative number.

Dark_Sun asks you to write a program to calculate the minimum total cost.

Input

Input will consist of multiple test cases.

The first line of each test case contains two integers N, K (1 ≤ N ≤ 105,0 ≤ K ≤ 10).

The next N - 1 lines, each line contains three integers u, v, w (0 ≤ u, v < N, |w| < 109, uv), indicating E(u, v) is w.

Output

For each case, output one line with one integer, indicating the minimum total cost.

Sample Input

3 2
0 1 2
1 2 2

Sample Output

8

Author: LU, Yi
Source: ZOJ Monthly, January 2015
Submit    Status