Cây khung nhỏ nhất

Cho đơn đồ thị vô hướng liên thông \(G = (V,E)\) gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ \(1\) đến \(n\) và các cạnh được đánh số từ \(1\) đến \(m\).

Biết cây khung của một đồ thị, đó chính là tập \(n\) đỉnh liên thông và tập các cạnh sao cho tổng trọng số của các cạnh là nhỏ nhất có thể.

Hãy tìm cây khung nhỏ nhất của đồ thị \(G\).

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n,m\).

• \(m\) dòng tiếp theo, dòng thứ \(i\) có dạng \(3\) số nguyên \(u, v, c\). Trong đó (\(u,v\)) là chỉ số hai đỉnh đầu mút của cạnh thứ \(i\) và \(c\) trọng số của cạnh đó.

Output

• Gồm \(1\) dòng duy nhất: Ghi tổng trọng số của cây khung nhỏ nhất.

Example

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

5