Minimum Cost to Connect Cities

You are given a set of cities and possible roads between them. Each road has a cost to upgrade. Your task is to determine the minimum total cost required to connect all the cities by selecting a subset of roads to upgrade. In other words, you need to find a Minimum Spanning Tree (MST) for the given graph.

If it is impossible to connect all cities, output -1.

The problem can be formulated as follows: Given a weighted undirected graph \(G=(V,E)\) with \(|V|=n\) and each edge \(e\) having a weight \(w(e)\), find a spanning tree \(T\) such that:

\[ \min_{T \subseteq E} \sum_{e \in T} w(e) \]

If no spanning tree exists that includes all vertices, the answer is -1.

inputFormat

The first line of input contains two integers (n) and (m) where (n) is the number of cities and (m) is the number of roads. Each of the next (m) lines contains three integers (u), (v), and (c), representing a road between cities (u) and (v) with an upgrade cost (c).

outputFormat

If it is possible to connect all the cities, output the minimum total cost on the first line, followed by (n-1) lines each containing two integers (u) and (v) representing the selected roads of the constructed MST. If it is impossible to connect all the cities, output -1.## sample

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

6
2 3
1 4
1 2

</p>