Cây Khung Bắt Buộc Từng Cạnh

Cho một đồ thị vô hướng liên thông có $n$ đỉnh và $m$ cạnh có trọng số. Đồ thị không có khuyên và không có hai cạnh nối cùng một cặp đỉnh.

Với từng cạnh theo thứ tự xuất hiện trong input, hãy tìm tổng trọng số nhỏ nhất của một cây khung bắt buộc chứa cạnh đó.

Input

• Dòng đầu chứa hai số nguyên $n,m$.
• Mỗi dòng trong $m$ dòng tiếp theo chứa ba số nguyên $u,v,w$, mô tả một cạnh nối $u$ với $v$ có trọng số $w$.

Output

• In $m$ dòng. Dòng thứ $i$ là tổng trọng số nhỏ nhất của một cây khung chứa cạnh thứ $i$ trong input.
• Nếu $m=0$, không in dòng nào.

Constraints

• $1\le n\le 2\cdot 10^5$.
• $n-1\le m\le 2\cdot 10^5$.
• $1\le u,v\le n,u\ne v$.
• $1\le w\le 10^9$.
• Đồ thị liên thông, không có khuyên và không có cạnh song song.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 7$ và $m\le 12$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4 5
1 2 1
2 3 2
3 4 3
1 4 10
1 3 4

6
6
6
13
8