E. Авиареформа
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Берляндия — большая страна с развитой системой авиасообщения. Всего в стране есть $$$n$$$ городов, которые исторически обслуживаются авиакомпанией Берляфлот. Авиакомпания выполняет двухсторонние рейсы между $$$m$$$ парами городов, $$$i$$$-й из них соединяет города с номерами $$$a_i$$$ и $$$b_i$$$ и имеет цену $$$c_i$$$ на перелёт в каждую из сторон.

Известно, что с помощью рейсов Берляфлота можно добраться от любого города до любого другого (возможно, с пересадками), а стоимость любого маршрута из нескольких стыковочных рейсов Берляфлота равна стоимости самого дорогого из них. Более формально, стоимость маршрута из города $$$t_1$$$ в город $$$t_k$$$ с $$$(k-2)$$$-мя пересадками в городах $$$t_2,\ t_3,\ t_4,\ \ldots,\ t_{k - 1}$$$ равна максимуму из стоимостей рейсов из города $$$t_1$$$ в $$$t_2$$$, из $$$t_2$$$ в $$$t_3$$$, из $$$t_3$$$ в $$$t_4$$$ и так далее до рейса из $$$t_{k - 1}$$$ в $$$t_k$$$. Разумеется, все эти рейсы должны выполняться авиакомпанией Берляфлот.

Недавно в Берляндии начала работать новая авиакомпания S8 Airlines. Эта авиакомпания совершает двусторонние рейсы между всеми парами городов, между которыми нет рейсов Берляфлота. Таким образом, между каждой парой городов есть рейс либо Берляфлота, либо S8 Airlines.

Стоимости рейсов авиакомпании S8 Airlines рассчитываются следующим образом: для каждой пары городов $$$x$$$ и $$$y$$$, между которыми выполняется рейс S8 Airlines, стоимость этого рейса равняется минимальной стоимости маршрута между городами $$$x$$$ и $$$y$$$ у Берляфлота в соответствии с описанным ранее ценообразованием.

Известно, что с помощью рейсов S8 Airlines можно добраться от любого города до любого другого с возможными пересадками, и, аналогично Берляфлоту, стоимость маршрута между любыми двумя городами стыковочными рейсами S8 Airlines равна стоимости самого дорогого рейса в этом маршруте.

Из-за увеличившейся конкуренции с S8 Airlines Берляфлот решил провести авиареформу и изменить стоимости своих рейсов. А именно, для $$$i$$$-го своего рейса между городами $$$a_i$$$ и $$$b_i$$$ Берляфлот хочет сделать стоимость этого рейса равной минимальной стоимости маршрута между городами $$$a_i$$$ и $$$b_i$$$ у авиакомпании S8 Airlines. Помогите менеджерам Берляфлота рассчитать новые стоимости рейсов.

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

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

В первой строке каждого набора входных данных водятся два целых числа $$$n$$$ и $$$m$$$ ($$$4 \le n \le 200\,000$$$, $$$n - 1 \le m \le 200\,000$$$, $$$m \le \frac{(n - 1) (n - 2)}{2}$$$) — число городов в Берляндии и число рейсов у Берляфлота.

В следующих $$$m$$$ строках описываются рейсы Берляфлота. В $$$i$$$-й строке даны три целых числа $$$a_i$$$, $$$b_i$$$ и $$$c_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$1 \le c_i \le 10^9$$$) — номера городов, которые соединены $$$i$$$-м рейсом Берляфлота, и стоимость $$$i$$$-го рейса Берляфлота.

Гарантируется, что никакой рейс не соединяет город сам с собой, а никакие 2 рейса не соединяют одну и ту же пару городов. Гарантируется, что рейсами Берляфлота можно добраться от любого города до любого другого и что рейсами S8 Airlines можно добраться от любого города до любого другого.

Обозначим за $$$N$$$ сумму значений $$$n$$$ по всем наборам входных данных, и за $$$M$$$ — сумму значений $$$m$$$ по всем наборам входных данных. Гарантируется, что $$$N, M \le 200\,000$$$.

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

Для каждого набора входных данных в отдельной строке выведите $$$m$$$ целых чисел, $$$i$$$-е из которых должно быть равно стоимости $$$i$$$-го рейса Берляфлота после авиареформы.

Пример
Входные данные
3
4 3
1 2 1
2 3 2
4 3 3
5 5
1 2 1
1 3 1
2 4 1
4 5 2
5 1 3
6 6
1 2 3
2 3 1
3 6 5
3 4 2
4 5 4
2 4 2
Выходные данные
3 3 3 
1 1 1 2 2 
4 4 5 3 4 4
Примечание

В примере в первом наборе входных данных авиакомпания S8 Airlines будет выполнять рейсы между парами городов: $$$(1, 3)$$$, $$$(1, 4)$$$ и $$$(2, 4)$$$.

Стоимость рейса между городами $$$1$$$ и $$$3$$$ будет равна $$$2$$$, так как минимальная стоимость маршрута Берляфлота равна $$$2$$$ — маршрут состоит из рейса между городами $$$1$$$ и $$$2$$$ стоимостью $$$1$$$ и рейса между городами $$$2$$$ и $$$3$$$ стоимостью $$$2$$$, максимум из стоимостей равен $$$2$$$.

Стоимость рейса между городами $$$1$$$ и $$$4$$$ будет равна $$$3$$$, так как минимальная стоимость маршрута Берляфлота составляет $$$3$$$ — маршрут состоит из рейса между городами $$$1$$$ и $$$2$$$ стоимостью $$$1$$$, рейса между городами $$$2$$$ и $$$3$$$ стоимостью $$$2$$$ и рейса между городами $$$3$$$ и $$$4$$$ стоимостью $$$3$$$, максимум из стоимостей равен $$$3$$$.

Стоимость рейса между городами $$$2$$$ и $$$4$$$ будет равна $$$3$$$, так как минимальная стоимость маршрута Берляфлота составляет $$$3$$$ — маршрут состоит из рейса между городами $$$2$$$ и $$$3$$$ стоимостью $$$2$$$ и рейса между городами $$$3$$$ и $$$4$$$ стоимостью $$$3$$$, максимум из стоимостей равен $$$3$$$.

После авиареформы стоимость рейса Берляфлота между городами $$$1$$$ и $$$2$$$ будет составлять $$$3$$$, так как минимальная стоимость маршрута S8 Airlines между этими городами составляет $$$3$$$ — маршрут состоит из рейса между городами $$$1$$$ и $$$4$$$ стоимостью $$$3$$$ и рейса между городами $$$2$$$ и $$$4$$$ стоимостью $$$3$$$, максимум равен $$$3$$$.

Стоимость рейса Берляфлота между городами $$$2$$$ и $$$3$$$ будет составлять $$$3$$$, так как минимальная стоимость маршрута S8 Airlines между этими городами составляет $$$3$$$ — маршрут состоит из рейса между городами $$$2$$$ и $$$4$$$ стоимостью $$$3$$$, рейса между городами $$$1$$$ и $$$4$$$ стоимостью $$$3$$$ и рейса между $$$1$$$ и $$$3$$$ стоимостью $$$2$$$, максимум равен $$$3$$$.

Стоимость рейса Берляфлота между городами $$$3$$$ и $$$4$$$ будет составлять $$$3$$$, так как минимальная стоимость маршрута S8 Airlines между этими городами составляет $$$3$$$ — маршрут состоит из рейса между городами $$$1$$$ и $$$3$$$ стоимостью $$$2$$$ и рейса между городами $$$1$$$ и $$$4$$$ стоимостью $$$3$$$, максимум равен $$$3$$$.

Во втором наборе входных данных у авиакомпании S8 Airlines будут следующие рейсы: между городами $$$1$$$ и $$$4$$$ стоимостью $$$1$$$, между городами $$$2$$$ и $$$3$$$ стоимостью $$$1$$$, между городами $$$2$$$ и $$$5$$$ стоимостью $$$2$$$, между городами $$$3$$$ и $$$4$$$ стоимостью $$$1$$$ и между городами $$$3$$$ и $$$5$$$ стоимостью $$$2$$$.