Берляндия — большая страна с развитой системой авиасообщения. Всего в стране есть \(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. Помогите менеджерам Берляфлота рассчитать новые стоимости рейсов.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите \(m\) целых чисел, \(i\)-е из которых должно быть равно стоимости \(i\)-го рейса Берляфлота после авиареформы.
Примечание
В примере в первом наборе входных данных авиакомпания 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|