C. Pleasant Paths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The map of the forest represents a rooted tree, where the vertices are clearings, the edges are paths between them, and the weight of an edge is the popularity of these paths. All clearings are numbered from $$$1$$$ to $$$n$$$.

Hedgehog Shurshik lives in the clearing located at the root vertex number $$$1$$$. During each of his walks, the hedgehog starts from vertex $$$1$$$ and goes to the leaf vertices for the tastiest apples, but only via a pleasant path. A pleasant path in the tree is a path from the root vertex to a leaf vertex such that at each descent, the hedgehog chooses the least popular road (i.e., descends along the edge with the smallest popularity value, and if there are several, to the vertex with the smallest number). A vertex is called a leaf if it has exactly one outgoing path and is not the root.

Shurshik made $$$q$$$ walks, each of which followed several rules: first, the hedgehog found a pleasant path, then added $$$+1$$$ to the popularity of all edges on the path. Help Shurshik determine how many times he will visit each leaf vertex.

Input

Each test consists of several testcases. The first line contains a single integer $$$t~(1 \le t \le 10^4)$$$ — the number of testcases. The following describes the testcases.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 10^{18}$$$) — the number of vertices in the tree and the number of walks made by Shurshik.

The next $$$n-1$$$ lines describe the edges of the tree. Each line contains three integers $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$0 \le w_i \le 10^{18}$$$) — the numbers of the vertices connected by the path and its initial popularity.

It is guaranteed that the sum of $$$n$$$ across all tests does not exceed $$$2 \cdot 10^5$$$ and the given graph is a tree with vertex $$$1$$$ as the root.

Output

For each testcase, output the information about the visits to the leaf vertices.

For each leaf vertex in ascending order of its number, output on a separate line two numbers: the leaf number and the number of times Shurshik visited this leaf during all $$$q$$$ walks.

Scoring
GroupPoints Additional Constraints Required Groups
112$$$\sum n \cdot q \le 2 \cdot 10^5$$$–
213$$$t = 1$$$; $$$n \le 20$$$; $$$w_i = 0$$$–
320$$$u_i = \lfloor \frac{i+1}{2} \rfloor$$$, $$$v_i = i+1$$$–
420$$$w_i = 0$$$ for all edges2
515$$$u_i = 1$$$, $$$v_i = i+1$$$–
620No additional constraints1, 2, 3, 4, 5
Example
Input
4
5 7
1 2 0
1 3 1
3 4 5
3 5 3
4 599
1 2 300
1 3 400
1 4 200
12 996179179
1 2 0
1 3 0
3 4 0
3 5 0
3 6 0
6 7 0
6 8 0
6 9 0
6 10 0
10 11 0
10 12 0
7 777
1 2 0
1 3 0
2 4 0
2 5 0
3 6 0
3 7 0
Output
2 4
4 1
5 2
2 200
3 100
4 299
2 498089590
4 166029863
5 166029863
7 41507466
8 41507466
9 41507466
11 20753733
12 20753732
4 195
5 194
6 194
7 194
Note

$$$\lfloor \frac{a}{b} \rfloor$$$ means rounding down the result of the division $$$\frac{a}{b}$$$. Thus, $$$\lfloor \frac{9}{10} \rfloor$$$ = 0 and $$$\lfloor \frac{1}{10} \rfloor$$$ = 0.