Minimum Spanning Tree of Zones

You are given a graph representing a set of zones (nodes) connected by roads (edges). Each road has an associated length (weight). Your task is to compute the Minimum Spanning Tree (MST) of the graph. A spanning tree is a subset of roads that connects all zones with exactly z - 1 roads (where z is the number of zones) and with minimum possible total length.

Recall that for a graph \(G=(V,E)\), a spanning tree is a set of edges \(T \subseteq E\) that connects all vertices and has \(|V|-1\) edges. The goal is to minimize the total cost given by \(\sum_{e \in T} w_e\), where \(w_e\) is the weight of the edge \(e\).

You can assume that the provided graph is connected whenever \(z \ge 2\), and if there is only one zone (\(z=1\)), then no road will be provided.

inputFormat

The input is given via standard input (stdin). The first line contains two integers: (z) (the number of zones) and (r) (the number of roads). The following (r) lines each contain three integers (u), (v), and (w), representing a road connecting zones (u) and (v) with length (w).

outputFormat

Output to standard output (stdout) exactly (z - 1) lines if (z > 1) (or nothing if (z = 1)). Each line should contain three integers (u), (v), and (w), representing a road in the Minimum Spanning Tree. The roads must be output in the order determined by the algorithm's processing (typically sorted by increasing weight).## sample

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

0 1 1
0 3 1
0 2 2