MST

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

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

5

Explanation

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

Example 2

4 2
1 2 1
3 4 1

-1