С вашей помощью Хайди подготовила план размещения ловушки и защиты. Однако внезапно из ТАРДИС выпрыгнул Доктор и сказал ей, что он шпионил за подготовкой Далеков, и что их больше, чем когда-либо. Отчаянные времена требует отчаянных мер, поэтому Хайди собирается рискнуть и встретится с Далеками и что она рассмотрит вариант размещения ловушки вдоль любого Коридора.
Это означает что ей опять нужна ваша помощь с вычислением \(E_{max}(c)\) — наибольшего \(e \le 10^9\), такого что если мы сменим требуемый уровень энергии у \(c\) на \(e\), то Далеки возможно воспользуются \(c\) в своём вторжении. Теперь нужно вычислить эту функцию для всех Временных Коридоров.
Первая строка содержит целые числа \(n\) и \(m\) (\(2 \leq n \leq 10^5\), \(n - 1 \leq m \leq 10^6\)) — количество точек и количество коридоров.
Каждая из следующих \(m\) строк содержит точки \(a\), \(b\) и уровень энергии \(e\) (\(1 \leq a, b \leq n\), \(a \neq b\), \(0 \leq e \leq 10^9\)).
Гарантируется, что ни одна пара \(\{a, b\}\) не повторяется и что граф является связным. Не гарантируется, что все уровни энергии \(e\) различны или что минимальное остовное дерево уникально.
Выведите \(m\) целых чисел: для каждого \(i\), \(E_{max}(c_i)\) для Коридора \(c_i\) из входных данных.
3 3 1 2 8 2 3 3 3 1 4
4 8 8
10000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач