eolymp
bolt
Try our new interface for solving problems
Problems

Reliable Nets

Reliable Nets

Time limit 1 second
Memory limit 122 MiB

You're in charge of designing a campus network between buildings and are very worried about its reliability and its cost. So, you've decided to build some redundancy into your network while keeping it as inexpensive as possible. Specifically, you want to build the cheapest network so that if any one line is broken, all buildings can still communicate. We'll call this a minimal reliable net.

Input data

There will be multiple test cases for this problem. Each test case will start with a pair of integers n (n15) and m (m20) on a line indicating the number of buildings (numbered 1 through n) and the number of potential inter-building connections, respectively. The following m lines are of the form b[1] b[2]c (all positive integers) indicating that it costs c to connect building b[1] and b[2]. All connections are bidirectional.

The last test case contains n = m = 0 and is not processed.

Output data

For each test case you should print one line giving the cost of a minimal reliable net. If there is a minimal reliable net, the output line should be of the form:

The minimal cost for test case p is c.

where p is the number of the test case (starting at 1) and c is the cost. If there is no reliable net possible, output a line of the form:

There is no reliable net possible for test case p.

prb2622 - Copy.gif

Examples

Input example #1
4 5
1 2 1
1 3 2
2 4 2
3 4 1
2 3 1
2 1
1 2 5
0 0
Output example #1
The minimal cost for test case 1 is 6.
There is no reliable net possible for test case 2.