Ферма Джона состоит из \(N\) пастбищ (\(2 \leq N \leq 50,000\)), попарно
соединённых \(N-1\) двунаправленными дорожками единичной длины. Известно также,
что имеется путь из любого пастбища к любому.
Однако если одну из дорожек заблокировать, то ферма разделится на две части,
внутри каждой из которых связность сохранится, а между ними - нет.
Поэтому ФД строит \(M\) дополнительных дорожек (\(1 \leq M \leq 50,000\)),
каждая из которых имеет положительную целую длину не более \(10^9\).
Коровы пользуются исходными дорожками, пока это возможно.
Если одна из изначальных дорожек становится заблокированной, ферма
становится несвязной и ФД выбирает из дополнительных дорожек, такую, которая
восстановит связность фермы, так чтобы коровы вновь могли ходить из любого
пастбища в любое.
Для каждой из исходных дорожек фермы, помогите ФД определить кратчайшую
подходящую дорожку из вновь построенных.
ФОРМАТ ВВОДА (файл disrupt.in):
Первая строка ввода содержит \(N\) и \(M\). Каждая из последующих \(N-1\) строк
описывает оригинальную дорожку целыми числами \(p\) \(q\), где \(p\) \neq q$
- пастбища, соединённые этой дорожкой (в интервале \(1 \ldots N\)).
Каждая из оставшихся \(M\) строк описывает дополнительную дорожку тремя
целыми числами \(p\), \(q\), \(r\), где \(r\) длина этой дорожки. Не более одной
дорожки пролегает между любыми двумя пастбищами.
ФОРМАТ ВЫВОДА (файл disrupt.out):
Для каждой из \(N-1\) оригинальных дорожек, в порядке как они появились
на вводе, выведите длину кратчайшей "замещающей" дорожки, которая восстановит
связность фермы в результате блокировки оригинальной дорожки.
Если такой дорожки не существует, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
1 2
1 3
4 1
4 5
6 5
2 3 7
3 6 8
6 4 5
|
7
7
8
5
5
|