Разрушение
Ферма Джона состоит из n пастбищ, попарно соединённых n − 1 двунаправленными дорожками единичной длины. Известно также, что имеется путь из любого пастбища к любому.
Однако если одну из дорожек заблокировать, то ферма разделится на две части, внутри каждой из которых связность сохранится, а между ними - нет. Поэтому ФД строит m дополнительных дорожек, каждая из которых имеет положительную целую длину не более 10^9. Коровы пользуются исходными дорожками, пока это возможно.
Если одна из изначальных дорожек становится заблокированной, ферма становится несвязной и ФД выбирает из дополнительных дорожек, такую, которая восстановит связность фермы, так чтобы коровы вновь могли ходить из любого пастбища в любое.
Для каждой из исходных дорожек фермы, помогите ФД определить кратчайшую подходящую дорожку из вновь построенных.
Входные данные
Первая строка содержит n (2 ≤ n ≤ 50000) и m (1 ≤ m ≤ 50000). Каждая из последующих n − 1 строк описывает оригинальную дорожку целыми числами p q, где p ≠ q − пастбища,соединённые этой дорожкой (в интервале 1..n). Каждая из оставшихся m строк описывает дополнительную дорожку тремя целыми числами p, q, r, где r длина этой дорожки. Не более одной дорожки пролегает между любыми двумя пастбищами.
Выходные данные
Для каждой из n − 1 оригинальных дорожек, в порядке как они появились на вводе, выведите длину кратчайшей "замещающей" дорожки, которая восстановит связность фермы в результате блокировки оригинальной дорожки. Если такой дорожки не существует, выведите -1.