Portal Network Optimization

You are given a network of n locations connected by p teleportation portals. Each portal connects two locations and has an associated teleportation time. Your task is to select exactly m portals such that the network remains fully connected while minimizing the maximum teleportation time among the chosen portals.

A common strategy is to first build a minimum spanning tree (MST) of the network to guarantee connectivity and then, if needed, add extra portals from the remaining ones to reach a total of m selected portals. If multiple valid solutions exist, you may output any one of them.

Note: It is guaranteed that m is at least n-1 so that a connected network is possible.

inputFormat

The first line contains three space-separated integers: n (number of locations), p (number of portals), and m (number of portals to select).

Each of the following p lines contains three space-separated integers: u, v, and t, indicating that there is a portal between locations u and v with teleportation time t.

outputFormat

Output exactly m lines, each containing three integers u, v, and t representing the portal's endpoints and its teleportation time. The order of output portals does not matter.

## sample

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

1 3 4
2 3 2
3 4 3

</p>