You are given an undirected weighted graph. Compute the total weight of a Minimum Spanning Tree (MST) of the graph.

If the graph is disconnected, it has no spanning tree; in that case output -1.

Input

The first line contains integers ~n~ and ~m~, the number of nodes and edges.

The following ~m~ lines each contain three integers ~a~, ~b~, and ~c~, describing an undirected edge between ~a~ and ~b~ with weight ~c~.

Nodes are numbered from ~1~ to ~n~.

Output

Output a single integer: the weight of an MST, or -1 if none exists.

Constraints

• ~1 \le n \le 10^5~
• ~0 \le m \le 2 \times 10^5~
• ~1 \le a, b \le n~
• ~1 \le c \le 10^9~

Example 1

Input

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

Output

5

Explanation

One MST uses edges of weights ~3~ and ~2~, for a total of ~5~.

Example 2

Input

4 2
1 2 1
3 4 1

Output

-1