Thành phố Hà Nội gồm 𝑛 nút giao thông và 𝑚 tuyến đường 2 chiều nối giữa 2 nút 𝑢𝑖 , 𝑣𝑖 (𝑢𝑖 ≠ 𝑣𝑖 ) có độ dài là 𝑤𝑖 . Ban lãnh đạo thành phố muốn chọn ra 𝑛 - 1 con đường trong 𝑚 tuyến đường có sẵn và cải tạo, nâng cấp, mở rộng chúng nhằm xây dựng hệ thống giao thông huyết mạch cho Hà Nội. Muốn vậy, các tuyến đường được chọn phải thỏa mãn: Từ một nút giao thông bất kì, có thể đến mọi nút giao thông khác; chỉ thông qua các con đường huyết mạch Để giảm thiểu tối đa chi phí, ban lãnh đạo muốn tìm một cách chọn các tuyến đường huyết mạch sao cho tổng độ dài của chúng là bé nhất. Tuy nhiên, cải thiện đường sá cũng gắn liền với đời sống của nhân dân; có một số tuyến đường mà nhân dân ở đó không cho phép cải tạo, khi đó ban lãnh đạo sẽ không chọn tuyến đường này vào hệ thống giao thông huyết mạch Với mỗi tuyến đường 𝑖, bạn hãy tìm cách chọn hệ thống giao thông huyết mạch có tổng độ dài các con đường là bé nhất nếu người dân sống trên con đường 𝑖 không đồng ý cho cải tạo (Coi như các tuyến đường khác, người dân đều cho nâng cấp)

Input

• Dòng đầu tiên chứa hai số nguyên ~𝑛~ và ~𝑚~ ~(1 ≤ 𝑛, 𝑚 ≤ 2 × 10^5 )~
• Số nút giao thông và số tuyến đường trên địa bàn thành phố Hà Nội.
• 𝑚 dòng tiếp, dòng thứ 𝑗 gồm ba số nguyên 𝑢𝑗 , 𝑣𝑗 , 𝑤𝑗 (1 ≤ 𝑢𝑗 , 𝑣𝑗 ≤ 𝑛, 𝑢𝑗 ≠ 𝑣𝑗 , 1 ≤ 𝑤𝑗 ≤ 10^9 ), mô tả tuyến đường thứ 𝑗 của Hà Nội

Output

• In ra ~𝑚~ dòng , dòng thứ ~𝑖~ in ra tổng độ dài bé nhất của tuyến đường huyết mạch nếu người dân trên con đường ~𝑖~ không cho cải tạo Nếu không thể dựng được một hệ thống tuyến đường huyết mạch, hãy in ra ~-1~.

Sample Input

4 6
1 2 2
1 3 6
1 4 3
2 3 1
2 4 4
3 4 5

Sample Output

8
6
7
10
6
6