D. Олимпиада в Берляндии
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

Международный олимпийский комитет наконец-то официально подтвердил, что следующие олимпийские игры состоятся в одном из городов Берляндии!

Конечно, страна ещё не готова к проведению Олимпиады, но впереди еще есть немного времени. Например, все дороги в Берляндии грунтовые, хотя по правилам МОК в стране проведения Олимпиады все города должны быть связаны высокоскоростными современными шоссе. В ходе дорожных работ некоторые (возможно, все) грунтовые дороги будут перестроены в шоссе. Другие способы прокладывать шоссе применяться не будут.

В Берляндии n городов, некоторые пары из которых соединены двусторонними грунтовыми дорогами. Для каждой дороги известно время tj, за которое её можно сделать высокоскоростным современным шоссе. В смету уже внесены всевозможные траты, поэтому основной критерий — подготовить страну к Олимпиаде как можно скорее.

В Олимпийском Комитете Берляндии было решено соединить некоторые города с помощью шоссе так, чтобы из каждого города было возможно доехать до любого другого используя только шоссе, но при этом должно быть проложено наименьшее возможное количество шоссе. На дорожные работы брошены силы большого числа рабочих бригад, поэтому работа на дорогах ведется параллельно. Таким образом, дорожные работы будут закончены за время, равное максимальному tj среди всех дорог, на которых ведутся работы.

Город, в котором будет проходить Олимпиада, еще не определен. Но в Олимпийском Комитете Берляндии уже решили, что для минимизации лишнего траффика к этому городу должно примыкать ровно одно шоссе.

Аналитическому отделу досталась непростая задача планирования работ. Для каждого города i найдите минимальное время на дорожные работы при условии, что именно город i будет принимать Олимпиаду.

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

Входные данные содержат один или несколько наборов тестовых данных, которые разделяются одиночными переводами строк.

Каждый набор начинается строкой, содержащей два целых числа n и m (2 ≤ n ≤ 4·105, 0 ≤ m ≤ 4·105), где n — количество городов в Берляндии, а m — количество грунтовых дорог. Все дороги являются двусторонними, между каждой парой городов не более одной дороги. Далее следует m строк, описывающих дороги. Строка j содержит три целых числа xj, yj и tj (1 ≤ xj, yj ≤ n) и обозначает, что j-ая дорога соединяет города xj и yj (xj ≠ yj), и требуется tj (1 ≤ tj ≤ 109) единиц времени на работы по прокладыванию шоссе на месте этой дороги.

Гарантируется, что суммарно по всем тестовым данным количество городов не превосходит 4·105, и количество дорог также не превосходит 4·105.

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

Для каждого набора тестовых данных выведите последовательность T1, T2, ..., Tn, где Ti — минимальное возможное время окончания дорожных работ при условии, что Олимпиада будет проведена в городе i. Выводите Ti =  - 1, если невозможно выполнить требования при проведении Олимпиады в городе i.

Следуйте формату из примера выходных данных.

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

3 3
1 2 1
2 3 1
3 1 2

3 2
1 2 2
2 3 4
Выходные данные
Case 1: 3 2 2 2
Case 2: 1 2 1
Case 3: 4 -1 4