Given a weighted undirected connected graph $G$ with $n$ vertices and $m$ edges, where all vertices are numbered $1, 2, \dots, n$.

Find the sum of the edge weights of the minimum spanning tree of $G$.

Input

The first line contains two positive integers $n$ and $m$.

The following $m$ lines each contain three positive integers $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $0 \le w_i \le 10^9$), describing an edge connecting vertices $u_i$ and $v_i$ with edge weight $w_i$.

Output

An integer representing the sum of the edge weights of the minimum spanning tree of $G$.

Examples

Input 1

7 12
1 2 9
1 5 2
1 6 3
2 3 5
2 6 7
3 4 6
3 7 3
4 5 6
4 7 2
5 6 3
5 7 6
6 7 1

Output 1

16

Subtasks

$1 \le n \le 2 \times 10^5$, $0 \le m \le 5 \times 10^5$.