Connecting Warehouses

We are given N warehouses and M transportation routes. Each route connects two warehouses with a cost. Your task is to find the minimum cost required to connect all the warehouses, forming a spanning tree. In other words, you are given an undirected weighted graph and you must compute its Minimum Spanning Tree (MST). The MST is defined as: $$ MST = \min_{T \subseteq E} \sum_{e \in T} w(e) $$, where T is a tree that spans all N nodes and (w(e)) is the cost of edge e. If it is not possible to connect all warehouses, print -1.

inputFormat

The input is read from standard input (stdin). The first line contains two integers N and M representing the number of warehouses and the number of transportation routes, respectively. Each of the following M lines contains three integers u, v, and w, representing a route from warehouse u to warehouse v with a cost w.

outputFormat

Output a single integer to standard output (stdout): the minimal cost required to connect all warehouses. If it is impossible to connect all warehouses, output -1.## sample

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

6