Cho đơn đồ thị liên thông vô hướng có trọng số trên cạnh gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm cây khung nhỏ nhất của đồ thị

Input

Dòng đầu chứa hai số n, m $(1<=n<=10000;1<=m<=20000)$

m dòng tiếp theo mỗi dòng chứa ba số nguyên u, v, w. Trong đó (u, v) là chỉ số hai đỉnh đầu mút còn w trọng số của cạnh đó $(1<=u,v<=n;1<=w<=1000)$

Output

Ghi ra một số nguyên là trọng số nhỏ nhất của cây khung

Ví dụ

Input

7 11
1 2 4
1 3 1
1 7 3
2 4 6
2 3 2
2 5 1
3 5 8
3 6 3
4 5 5
5 6 2
5 7 3

Output

14