Minimum Cost to Connect All Nodes

You are given an undirected weighted graph with n nodes and m edges. Your task is to determine the minimum cost required to connect all nodes (i.e. to form a spanning tree). If it is not possible to connect all nodes using the given edges, print -1.

The cost of the spanning tree is defined as the sum of the weights of the selected edges. In other words, if the set T represents the edges of the spanning tree, then the cost is

$$\text{Cost}(T) = \sum_{e \in T} w(e)$$

If the graph is already connected, the answer is simply the cost of the minimum spanning tree (MST). Otherwise, if the graph is disconnected such that even after selecting all possible edges you cannot connect all components, output -1.

Note: The input edges are 1-indexed.

inputFormat

The first line contains two integers n and m, where n is the number of nodes and m is the number of edges. The following m lines each contain three integers u, v, and w representing an edge between nodes u and v with weight w.

Input format:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

outputFormat

If it is possible to connect all nodes, output a single integer representing the minimum cost to do so. Otherwise, output -1.

Output format:

result

## sample

4 3
1 2 1
2 3 2
3 4 3

6