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 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ị G.

Input

Dòng 1: Chứa hai số n, m (1 <= n <= 10,000; 1 <= m <= 15,000)

M dòng tiếp theo, dòng thứ i có dạng ba 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 đó (1 <= u, v <= n; 0 <= c <= 10,000).

Output

Gồm 1 dòng duy nhất: Ghi trọng số cây khung nhỏ nhất

Example

Input  
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  
  
Output  
5