Bác nông dân John tự hào vì điều hành một trang trại có khả năng kết nối tốt. Trang trại gồm \(N\) đồng cỏ (\(2 \leq N \leq 50\,000\)), được nối với nhau bằng \(N-1\) đường đi hai chiều có độ dài bằng một. Bác nông dân John nhận thấy rằng bằng cách sử dụng một chuỗi thích hợp gồm các đường đi này, ta có thể di chuyển từ bất kỳ đồng cỏ nào tới bất kỳ đồng cỏ nào khác.

Mặc dù trang trại được kết nối, bác nông dân John lo lắng về điều có thể xảy ra nếu một đường đi bị chặn, vì khi đó trang trại sẽ bị chia thành hai tập đồng cỏ rời nhau: đàn bò có thể di chuyển trong từng tập nhưng không thể di chuyển giữa hai tập. Vì vậy, ông xây thêm một tập gồm \(M\) đường đi hai chiều (\(1 \leq M \leq 50\,000\)), mỗi đường có độ dài là một số nguyên dương không vượt quá \(10^9\). Đàn bò vẫn chỉ sử dụng các đường đi ban đầu để di chuyển, trừ khi một trong số chúng bị chặn.

Nếu một trong các đường đi ban đầu bị chặn, trang trại sẽ bị chia thành hai phần rời nhau. Bác nông dân John sẽ chọn đúng một đường thay thế trong số các đường bổ sung để khôi phục kết nối giữa hai phần, nhờ đó đàn bò lại có thể di chuyển từ bất kỳ đồng cỏ nào tới bất kỳ đồng cỏ nào khác.

Với mỗi đường đi ban đầu trong trang trại, hãy giúp bác nông dân John chọn đường thay thế phù hợp ngắn nhất.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một đường đi ban đầu bằng hai số nguyên \(p\), \(q\), trong đó \(p \ne q\) là hai đồng cỏ được đường đi nối với nhau và đều thuộc khoảng \(1 \ldots N\). Mỗi dòng trong \(M\) dòng còn lại mô tả một đường đi bổ sung bằng ba số nguyên \(p\), \(q\) và \(r\), trong đó \(r\) là độ dài của đường đi. Giữa mỗi cặp đồng cỏ có nhiều nhất một đường đi.

Dữ liệu ra

Với mỗi đường trong \(N-1\) đường đi ban đầu, theo đúng thứ tự chúng xuất hiện trong dữ liệu vào, in độ dài của đường thay thế phù hợp ngắn nhất có thể kết nối lại trang trại nếu đường ban đầu đó bị chặn. Nếu không tồn tại đường thay thế phù hợp, in -1.

Ví dụ

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

Nguồn

USACO 2018 US Open Contest, Platinum — Disruption

Tác giả bài toán: Brian Dean.