Problem
Caiman has an unusual dream, that he is in a strange part of the city. This area can be represented as a tree graph, where the vertices are intersections and the edges are two-way roads that connect these intersections. There are n intersections in total and each has its own number from 0 to n-1.
But not everything is so bad in this dream, because on every road between intersections with numbers u and v there are C
u,v dumplings! Caiman loves dumplings very much, so he wants to eat as much as possible, but there is a problem - if he visits any crossroads more than k times, he will be attacked by an evil dumpling monster.
Although this is a dream, the dumplings on each road can only be eaten once, although nothing prevents you from walking along the roads several times. Also Cayman does not stop on the roads. That is, if he starts to move from one intersection to another, then he will definitely go all the way to the next intersection.
At the beginning of the dream, Caiman is at the crossroad number 0. Help him determine the maximum number of dumplings he can eat without being attacked by the evil dumpling monster.
Input:
The first line contains two integers n and k (3 ≤ n ≤ 10
5; 1 ≤ k ≤ 10
5) &mdash ; the number of intersections and the maximum number of visits to each of the intersections.
The next n - 1 lines contain three integers u, v and C
u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C
u,v< /sub> ≤ 10000), meaning that the intersections with numbers u and v are connected by a road with Cu,v dumplings.
It is guaranteed that intersections and roads form a tree.
Output:
Print a single integer - the maximum number of dumplings Caiman can eat.
Examples:
| Input |
Output |
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 15 |
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 17 |
11 6
1 0 7932
21 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
| 54092 |
Explanation:
In the first example, you need to visit intersections in the following order: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, ?2, ?8. Then he will eat a total of 1+2+2+1+3+3+3 = 15 dumplings.
Note that no intersection is visited more than 3 times.