Problem C
Landline Telephone Network

The mayor of RMRCity wants to create a secure landline telephone network for emergency use in case of serious disasters when the city is cut off from the outside world. Some pairs of buildings in the city can be directly connected with a wire telephone line and the municipality engineers have prepared an estimate of the cost of connecting any such pair.
The mayor needs your help to find the cheapest network that
connects all buildings in the city and satisfies a particular
security measure that will be explained shortly. A call from a
building
Input
The input consists of a single test case. The first line
contains three integers
Output
Display the cost of the cheapest network satisfying the security measure if it is possible. Otherwise, display impossible.
Sample Input 1 | Sample Output 1 |
---|---|
4 6 1 1 1 2 1 1 3 1 1 4 1 2 3 2 2 4 4 3 4 3 |
6 |
Sample Input 2 | Sample Output 2 |
---|---|
4 3 2 1 2 1 2 1 2 3 7 3 4 5 |
impossible |