MST Lighting Problem

In this problem, you are given a graph representing houses and the roads connecting them. Each road has an associated positive weight. The goal is to install lights along a minimal set of roads such that all houses remain connected by a lighted path. In other words, you need to compute the Minimum Spanning Tree (MST) of the graph using, for example, Kruskal’s algorithm.

Recall that an MST of a connected graph with (n) vertices is a subset of the edges that connects all vertices together without any cycles and with the minimum possible total edge weight. Your task is to output the number of edges in the MST and list each edge chosen for the MST.

Input/Output Format:

• The first line of input contains two integers \(n\) and \(m\), where \(n\) is the number of houses and \(m\) is the number of roads.
• The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\) indicating a road connecting house \(u\) and house \(v\) with weight \(w\).
• Output should consist of the number of edges in the MST on the first line, followed by each chosen edge on a new line in the format: \(u\) \(v\) \(w\).

inputFormat

The input is given via standard input (stdin). The first line contains two integers (n) and (m) separated by a space. The following (m) lines each contain three integers representing an edge: (u), (v) (the endpoints of the edge), and (w) (the weight of the edge).

outputFormat

The output should be printed to standard output (stdout). The first line of output should be an integer representing the number of edges in the MST. Each subsequent line should list an edge in the MST in the format: (u) (v) (w).## sample

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

3
1 2 1
1 3 2
2 4 3