Руйнування
Ферма Джона складається з 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.