Optical Network
By OBI - Olimpíada Brasileira de Informática 2000 
Brazil
By OBI - Olimpíada Brasileira de Informática 2000 Brazil
The caciques of Tutuaçu region intend to integrate their tribes called the "global village". The first step was the distribution of mobile phones to all shamans. Now, they plan to set up an optical fiber network connecting all tabas. This contract requires that new bites are opened in the woods, through the flora and fauna reserves. Aware of the need to preserve as much as possible the environment, the chiefs commissioned a study of the environmental impact of the project. Can you help them design the fiber optic network?
We will call an optical fiber connection between two tabas a branch network. To enable communication between all tabas is necessary that all of them are connected directly (using a branch network) or indirectly (using more than one branch). The caciques managed the environmental impact information that will cause the construction of branches. Some branches, however, were not considered in the environmental study because their construction is impossible.
Your task is to write a program to determine which branches are to be built, in order to enable communication between all tabas, causing the least possible environmental impact.
The input consists of several test sets. The first line of a test set contains two positive integers N (0 ≤ N ≤ 100) e M (1 ≤ M ≤ N(N-1)/2) indicating respectively the number of lands and the possible number of network branches. The tabas are numbered from 1 to N. The M following lines contain three positive integers X, Y e Z (1 ≤ X,Y,Z ≤ 100), that indicate that the network branch which connects the taba X to taba Y has environmental impact Z. With data test sets it is always possible to interconnect all tabas. The end of input is indicated when N = 0.
For each entry test set your program should produce a list of the branches of networks that must be built. The list must be preceded by a line that identifies the test set, in the form "Teste n", where n is numbered from 1. The list consists of a sequence of branches to be built, for a branch line. A branch is depicted by a pair of tabas X e Y , with X < Y. The network branches can be listed in any order, but should not be repeated. If there is more than one possible solution, print only one. The end of the list of branches is marked with a blank line. The spelling shown in Example output below should be followed strictly.
| Input Sample | Output Sample |
|
3 3 1 2 8 2 3 8 3 1 10 5 6 1 2 14 1 3 11 2 4 12 2 5 4 3 2 5 3 4 5 0 0 |
Teste 1 1 2 2 3 Teste 2 2 5 2 3 3 4 1 3 |