Порушення#10392
Фермер Джон пишається тим, що керує добре зв'язаним господарством. Ферма складається з пасовищ, з'єднаних n - 1 двосторонніми стежками, кожна одиничної довжини. Фермер Джон помічає, що, використовуючи відповідну послідовність цих стежок, можна дістатися з будь-якого пасовища до будь-якого іншого.
Хоча ферма ФД є зв'язною, він турбується про те, що може статися, якщо одна зі стежок буде заблокована: це розділить його ферму на дві непересічні множини пасовищ, так що корови зможуть пересуватися в межах кожної множини, але не між множинами. Тому ФД будує додаткових двосторонніх стежок, кожна з яких має довжину — додатне ціле число, що не перевищує 10^9. Корови все ще використовують лише початкові стежки, доки одна з них не стане заблокованою.
Якщо одна з початкових стежок стає заблокованою, ферма розділяється на дві непересічні частини, і ФД обирає одну з додаткових стежок як заміну, яка знову з'єднує ці дві частини, так що корови знову можуть дістатися з будь-якого пасовища до будь-якого іншого.
Для кожної з початкових стежок допоможіть ФД обрати найкоротшу придатну стежку-заміну.
Перший рядок містить два цілих числа і m~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 5 \cdot 10^4). Кожен з наступних n - 1 рядків описує початкову стежку і містить два цілих числа і q~(1 \le p, q \le n, p \ne q) — пасовища, з'єднані цією стежкою. Кожен з наступних рядків описує додаткову стежку і містить три цілих числа , та , де і — пасовища, які вона з'єднує, а — її довжина. Будь-яка пара пасовищ з'єднана щонайбільше однією стежкою.
Для кожної з n - 1 початкових стежок, у порядку їх появи у вхідних даних, виведіть довжину найкоротшої придатної стежки-заміни, яка б знову з'єднала ферму, якби ця початкова стежка була заблокована. Якщо придатної заміни не існує, виведіть -1.
Приклад 1