eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Разрушение

Разрушение

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Ферма Джона состоит из n пастбищ, попарно соединённых n1 двунаправленными дорожками единичной длины. Известно также, что имеется путь из любого пастбища к любому.

Однако если одну из дорожек заблокировать, то ферма разделится на две части, внутри каждой из которых связность сохранится, а между ними - нет. Поэтому ФД строит m дополнительных дорожек, каждая из которых имеет положительную целую длину не более 10^9. Коровы пользуются исходными дорожками, пока это возможно.

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

Для каждой из исходных дорожек фермы, помогите ФД определить кратчайшую подходящую дорожку из вновь построенных.

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

Первая строка содержит n (2 ≤ n ≤ 50000) и m (1m50000). Каждая из последующих n1 строк описывает оригинальную дорожку целыми числами p q, где pq − пастбища,соединённые этой дорожкой (в интервале 1..n). Каждая из оставшихся m строк описывает дополнительную дорожку тремя целыми числами p, q, r, где r длина этой дорожки. Не более одной дорожки пролегает между любыми двумя пастбищами.

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

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

Пример

Входные данные #1
6 3
1 2
1 3
4 1
4 5
6 5
2 3 7
3 6 8
6 4 5
Выходные данные #1
7
7
8
5
5
Источник 2018 USACO US Open, Платина