Задача №114639. Дороги в стране
В некоторой стране есть \(n\) городов, пронумерованных целыми числами от \(1\) до \(n\). Столица этой страны расположена в городе с номером \(1\). Некоторые пары городов в этой стране соединены дорогами с односторонним движением, при этом для каждой пары городов \(u\) и \(v\) есть не более одной дороги, ведущей из города \(u\) в город \(v\), однако наличие дороги из города \(u\) в город \(v\) не запрещает существование дороги из города \(v\) в город \(u\). Для каждой дороги известно, груз какого максимального веса можно по ней перевозить. Требуется для каждого города определить максимальный вес груза, который можно доставить из него в столицу.
В первой строке содержатся два целых числа \(n\) и \(m\) (\(2 \le n \le 10^5\), \(0 \le m \le 10^6\)) — количество городов и дорог в стране, соответственно.
В следующих \(m\) строках содержатся описания дорог. Описание дороги состоит из трёх целых чисел \(u\), \(v\) и \(w\) (\(1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 10^9\)), описывающих дорогу с односторонним движением из города с номером \(u\) в город с номером \(v\), по которой можно перевозить грузы весом не более \(w\). Гарантируется, что для каждой пары городов \(u\) и \(v\) существует не более одной дороги из \(u\) в \(v\).
Выведите \(n - 1\) целых чисел. \(i\)-е число должно быть равно максимальному весу груза, который можно перевезти из города \(i + 1\) в столицу (город с номером \(1\)). Если из города \(i + 1\) в столицу доставить груз невозможно, то выведите \(-1\).
В первом примере есть только одна дорога, заканчивающаяся в столице, и по ней нельзя везти грузы весом более \(1\), при этом из всех городов можно доехать до столицы по дорогам. Таким образом, из всех городов можно привезти в столицу груз весом не более \(1\).
Во втором примере из города \(2\) в город \(1\) можно перевезти груз весом \(3\) следующим образом: проехать из города \(2\) в город \(3\) по дороге, по которой можно везти грузы весом не более \(3\), а затем из города \(3\) в столицу (город \(1\)) по дороге, по которой можно везти грузы весом не более \(7\). Из города \(3\) в город \(1\) можно доставить груз весом \(7\) по прямой дороге, соединяющей эти города. Аналогично, из горда \(4\) в город \(1\) можно перевезти груз весом \(1\) по дороге, соединяющей эти города напрямую.
В третьем примере из города \(3\) в столицу доехать нельзя.
4 4 1 2 3 2 3 6 3 4 2 4 1 1
1 1 1
4 5 2 3 3 3 1 7 2 1 2 2 4 9 4 1 1
3 7 1
3 2 2 1 2 1 3 2
2 -1