Given an undirected graph with ~n~ vertices and ~m~ edges. Find minimum spanning tree and calculate its total length, if you cannot form the tree, print ~-1~.

Input

• First line contains ~n~ and ~m~ ~(n, m \le 10^5)~
• Next ~m~ lines, each line contains three integers represent for and edge: vertex1, vertex2 and length

Output

• Print the minimum spanning tree's total length if found, otherwise print ~-1~

Example Input 1

5 35 3
2 1 97
1 3 37
2 0 11

Example Output 1

-1

Sample Input 2

5 35 10
4 1 48
4 2 53
1 3 62
0 1 54
3 2 64
0 4 61
1 2 41
4 3 7
3 0 63
2 0 43

Sample Output 2

139