Задача №724. Берляндия атакует
В этой задаче Вам вновь придется помочь Берляндии. Эта страна состоит из \(n\) городов, некоторые пары из которых соединены двусторонними дорогами, каждая дорога характеризуется своей длиной. Все города пронумерованы числами от 1 до \(n\), столица имеет номер 1. Время от време ни Президент объезжает страну, посещая города страны. Целью каждой поездки является один из городов, к которому он едет из столицы вдоль дорог одним из кратчайших путей.
В далекие времена (когда задачи на алгоритм Дейкстры вызывали сложность) специальное ведомство составила такой набор дорог \(T\), вдоль которого можно было проехать из столицы в любой город, причем единственным образом. Разумеется, путь по дорогам из набора \(T\) из столицы в каждый город являлся кратчайшим. Особо умные жители страны попросту называли этот набор дорог "деревом кратчайших путей". Известно, что Президент пользовался дорогами из \(T\) во время своих поездок. За прошедшие годы этот набор перестал быть секретным, и, поэтому, стал объектом повышенного внимания берляндских экстремистов. У специального ведомства новое задание. Для каждого города кроме столицы необходимо вычислить кратчайшее расстояние до него, при условии, что та дорога по которой Президент должен был закончить свой путь в этот город является атакованной и проезжать по ней нельзя.
В первой строке входного файла записана пара целых чисел \(n\) и \(m\) (\(2 \leq n \leq 4\,000\); \( n - 1 \leq m \leq 100\,000\)), где \(n\) — количество городов в стране, а \(m\)— количество дорог в этой стране. Далее в \(m\) строках содержатся описания дорог, по одной дороге в строке. Каждая дорога задается четверкой целых чисел \(a_j\), \(b_j\), \(l_j\), \(t_j\) , где \(a_j\), \(b_j\) это номера городов, соединяемых дорогой (\(1 \leq a_j, b_j \leq n\); \(a_j \neq b_j\)), \(l_j\) — ее длина (\(1 \leq l_j \leq 10^5\)), а \(t_j\) равно 1 если дорога принадлежит дереву кратчайших путей и 0 в противном случае.
Гарантируется, что набор \(T\) удовлетворяет описанным выше свойствам. Между парой городов может быть более одной дороги. Все дороги двусторонние.
Выведите \(n - 1\) число в строку через пробелы. \(i\)-ое число должно быть равно либо длине кратчайшго пути из столицы в город \(i + 1\), при условии, что по той дороге из \(T\), которой Президент заканчивал свой путь в этот город, передвигаться нельзя, либо -1, если добраться до города \(i + 1\) вообще невозможно.
5 9 3 1 3 1 1 4 2 1 2 1 6 0 2 3 4 0 5 2 3 0 3 2 2 1 5 3 1 1 3 5 2 0 4 5 4 0
6 7 8 5