New Campus
By Ricardo Oliveira, UFPR 
Brazil
By Ricardo Oliveira, UFPR Brazil
The Federal University of the Pinheiros Republic (FUPR) is building a new campus in the capital.
Right now, all N buildings of the campus are built and ready to open! However, no paths between those buildings were built. Today, it is impossible to leave a building and go to another building in the campus!
To solve this problem, the FUPR dean wants to build paths between pairs of buildings such that all buildings are connected, i.e., such that, using one or more paths, it is possible to leave any building and go to any other building in the campus.
However, due to the complicated geography of the capital, it might not be possible to build a path between any pair of buildings. Given the list of paths that can be built and the cost of building each path, determine wheter it is possible to connect all buildings, and, if it is, the minimum total cost needed to build the necessary paths.
The input contains several test cases. The first line of each test case contains two integers N and M (2 ≤ N ≤ 1000, 0 ≤ M ≤ N(N-1)/2), the number of buildings and the number of paths that can be built, respectively. Buildings are numbered from 1 to N. The next M lines describe the paths. Each line contains three integers A, B and C (1 ≤ A, B ≤ N, A≠B, 1 ≤ C ≤ 104), indicating it is possible to build a path between buildings A and B and its cost is C dollars. It is guaranteed that, for each pair of buildings, at most one path can be built between them.
The input ends with end-of-file (EOF).
For each test case, if it is not possible to connect the buildings, print a line containing “impossivel” (without quotes). Otherwise, print a line containing the minimum total cost needed to connect all buildings, in dollars.
| Input Sample | Output Sample |
|
4 5 |
75 |