C. Приятные пути
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Карта леса представляет собой корневое дерево, вершины которого — поляны, рёбра — тропинки между ними, а вес ребра — протоптанность этих тропинок. Все поляны пронумерованы от $$$1$$$ до $$$n$$$.

Ёжик Шуршик живёт на поляне, которая находится в вершине-корне под номером $$$1$$$. Во время каждой своей прогулки ёжик отправляется из вершины $$$1$$$ и идёт в вершины-листья за самыми вкусными яблоками, но только приятным путём. Приятный путь в дереве — путь из вершины-корня в вершину-лист такой, что при каждом спуске ёжик выбирает самую непопулярную дорогу (т.е. спускается по ребру с наименьшим значением протоптанности, а если таких несколько — в вершину с наименьшим номером). Вершина называется листом, если из неё исходит ровно одна тропинка, и она не является корнем.

Шуршик совершил $$$q$$$ прогулок, каждая из которых проходила по нескольким правилам: сначала ёжик находил приятный путь, затем ко всем рёбрам пути добавлял $$$+1$$$ к их протоптанности. Помогите Шуршику определить, сколько раз он побывает в каждой листовой вершине.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t~(1 \le t \le 10^4)$$$  — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 10^{18}$$$) — количество вершин в дереве и количество прогулок Шуршика.

Следующие $$$n-1$$$ строк описывают рёбра дерева. Каждая строка содержит три целых числа $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$0 \le w_i \le 10^{18}$$$) — номера вершин, соединённых тропинкой, и её начальная протоптанность.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$2 \cdot 10^5$$$ и заданный граф является деревом, корнем которого является вершина $$$1$$$.

Выходные данные

Для каждого теста выведите информацию о посещениях листовых вершин.

Для каждой листовой вершины в порядке возрастания её номера выведите в отдельной строке два числа: номер листа и количество раз, которое Шуршик побывал в этом листе за все $$$q$$$ прогулок.

Система оценки
ГруппаБаллы Дополнительные ограничения Необходимые группы
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$$$ для всех рёбер2
515$$$u_i = 1$$$, $$$v_i = i+1$$$–
620Нет дополнительных ограничений1, 2, 3, 4, 5
Пример
Входные данные
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
Выходные данные
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
Примечание

$$$\lfloor \frac{a}{b} \rfloor$$$ означает округление вниз результата деления $$$\frac{a}{b}$$$. Так $$$\lfloor \frac{9}{10} \rfloor$$$ = 0 и $$$\lfloor \frac{1}{10} \rfloor$$$ = 0.