Minimum Spanning Road Network

You are given a connected undirected graph representing a road network. The graph has n intersections and m roads. Each road is described by three integers u, v and w, which represent a road between intersections u and v with length w. Your task is to compute the minimum total length of roads required to connect all intersections, i.e., to build a Minimum Spanning Tree (MST) of the graph.

The problem can be formally formulated as: Given a connected graph \(G=(V,E)\) with \(|V|=n\) and weighted edges \(E\), find a subset \(T\subseteq E\) such that \(T\) connects all vertices and \(\sum_{e \in T} w(e)\) is minimized.

Note: It is guaranteed that the graph is connected, so an MST always exists.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains two integers n (number of intersections) and m (number of roads).
• The following m lines each contain three integers u, v, and w representing a road between intersections u and v with length w.

outputFormat

Output a single integer to stdout representing the minimum total road length required to connect all the intersections.

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

7