Minimum Spanning Tree

You are given a connected, undirected graph with N intersections and M bidirectional roads. Each road has an associated length. Your task is to compute the minimal sum of the road lengths that can connect all the intersections, i.e., the sum of the edge weights in a minimum spanning tree (MST).

The problem can be formally described as follows:

Given a graph \(G=(V,E)\) where \(|V|=N\) and each edge \((u,v)\in E\) has a weight \(L_{uv}\), find a subset \(E'\subseteq E\) that connects all vertices and minimizes \(\sum_{(u,v)\in E'} L_{uv}\).

You may assume that the graph is connected so that an MST always exists.

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

• The first line contains two integers N and M representing the number of intersections and number of roads respectively.
• The next M lines each contain three integers: u, v, and L representing a bidirectional road connecting intersections u and v with length L.

Note: Intersections are numbered from 1 to N.

outputFormat

The output should be written to standard output (stdout). It consists of a single integer which is the total weight of the edges in the minimum spanning tree.

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

3