Minimum Spanning Tree

You are given an undirected weighted graph with N nodes and M edges. Your task is to compute the sum of the weights of the edges that form the Minimum Spanning Tree (MST) of the graph. If an MST does not exist (i.e., the graph is disconnected), output \(-1\).

The MST of a graph is a spanning tree whose total edge weight is minimized. Formally, if the set of edges chosen is \(E'\), then you must minimize \(\sum_{e \in E'} w(e)\) under the constraint that \((V, E')\) is a tree spanning all vertices.

inputFormat

The input is provided via standard input in the following format:

N M
u1 v1 w1
u2 v2 w2
... 
uM vM wM

Here, the first line contains two integers \(N\) and \(M\), the number of nodes and edges respectively. Each of the next \(M\) lines contains three integers \(u_i\), \(v_i\) and \(w_i\) representing an edge between nodes \(u_i\) and \(v_i\) with weight \(w_i\). Nodes are numbered from 1 to \(N\).

outputFormat

Output a single integer via standard output: the total weight of the MST. If it is not possible to construct an MST (i.e. the graph is disconnected), output \(-1\).

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

9