Connecting Cities with New Highways

Given n cities and m existing roads, you are required to construct k new highways to connect disjoint cities. The new highways should be selected such that they are not already present among the given road connections and their lengths are minimized. For simplicity, the length of a highway built between city i and city j is defined as \(i+j\).

Your task is to iterate over all pairs of cities (i, j) with \(i < j\) in increasing order, and select the first k pairs that are not already connected by an existing road. Output each highway as a line containing three integers: the two city numbers and the highway length.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(k\): the number of cities, the number of existing roads, and the number of new highways to construct, respectively.

This is followed by \(m\) lines. Each line contains three integers \(a\), \(b\), and \(l\), representing a road connecting city \(a\) and city \(b\) with length \(l\).

outputFormat

Output exactly \(k\) lines. Each line should contain three integers: the two cities that are connected by the new highway, and the length of that highway (which is defined as \(i+j\) for a highway connecting cities \(i\) and \(j\)).

4 3 2
1 2 5
2 3 7
3 4 8

1 3 4
1 4 5