D. Лучший вес для ребра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан связный неориентированный взвешенный граф с n вершинами и m ребрами. Граф не содержит петель и мультиребер. Рассмотрим некоторое ребро с номером i. Для него определим наибольший возможный вес, который можно присвоить этому ребру, чтобы оно содержалось во всех минимальный покрывающих деревьях данного графа.

Требуется для каждого ребра посчитать максимальный вес по описанным правилам. При этом для каждого ребра ответ должен считаться независимо, то есть в графе может существовать максимум одно ребро с измененным весом.

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

В первой строке даны через пробел два целых положительных числа n и m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105), где n и m — количество вершин и ребер графа соответственно.

В следующих m строках даны по три числа u, v и c (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ c ≤ 109), означающие, что между вершинами u и v есть ребро с весом c.

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

В единственной строке выведите через пробел искомые веса ребер в том порядке, в котором они заданы во входных данных. Если ребро при любом весе будет содержаться во всех покрывающих деревьях, выведите для него -1.

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