On yet another of his adventures, Brian Bipai loses his way in an underground network of tunnels. Fortunately, he brought a map with him.

The map of the tunnel system identifies a series of $N$ points labelled from $1$ to $N$. There are $N-1$ tunnels that each connect a distinct pair of points $(A,B)$ with a distance of $C$. Each point can be reached from any other point by exactly one pathway of tunnels.

Brian Bipai does not know which of the points on the map he is located at. He knows that an exit must exist somewhere, but not where it is. However, he observes (based on his nearby surroundings) that he is definitely located at a point with $T$ connecting tunnels.

Brian Bipai would like you to determine all points on the map where he could potentially be at. Furthermore, for each of those points $P_i$, determine the minimum distance $D_i$ that he has to travel in order to optimally search the entire underground network of tunnels for the exit.

Constraints

$1\le N\le 200000$

$1\le T\le N-1$

$1\le A_i,B_i\le N$

$1\le C_i\le 5000$

For $50\mathrm{\%}$ of the points, $1\le N\le 2000$.

Input Specification

The first line contains two integers $N$ and $T$.

The following $N-1$ lines each contain three spaced integers: $A_i$, $B_i$, and $C_i$.

Output Specification

For each possible point that Brian Bipai could be at, print $P_i$ and $D_i$ separated by a space on its own line. All $P_i$ must be stated in increasing order.

Sample Input

6 3
1 3 1
2 3 1
3 4 3
4 5 2
4 6 2

Sample Output

3 13
4 14

Explanation

Brian Bipai could be located at point $3$ or point $4$.
If he begins at point $3$, then his optimal search path would be $3\to 1\to 3\to 2\to 3\to 4\to 5\to 4\to 6$, taking a total distance of $13$.
If he begins at point $4$, then his optimal search path would be $4\to 5\to 4\to 6\to 4\to 3\to 1\to 3\to 2$, taking a total distance of $14$.