RELINETS  Reliable Nets
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
There will be multiple test cases for this problem. Each test case will start with a pair of integers n (<=15) and m (<= 20) on a line indicating the number of buildings (numbered 1 through n) and the number of potential interbuilding connections, respectively. (Values of n = m = 0 indicate the end of the problem.) 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.
Output
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.
Example
Input: 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: The minimal cost for test case 1 is 6. There is no reliable net possible for test case 2.
hide comments
vineetjai:
20201108 09:45:57
O(2^m*m*m) complexity passed. 

nadstratosfer:
20191201 05:45:08
Cool problem. Enjoyed everything between coding 2 wrong solutions and a testcase generator, lengthy analysis of what can be going wrong and finally an unexpected AC in PyPy with not really the most elegant code I've ever produced. 

Antonio Roberto Paoli:
20180926 18:35:27
A semiEulerian graph (a graph with exact 2 nodes with grade 3) is reliable too. I think the solution asked does not consider this hipotesis. So this test case would be reliable.


herambpatil98:
20180629 16:15:57
Last edit: 20180629 16:16:21 

shubham_9008:
20180516 17:38:42
pls sb give a suggestion on how to solve this problem


shiv2111:
20180118 08:31:09
easy peasy : 

sxie12:
20170629 23:49:31
Don't compare with spojtoolkit. It has an incorrect solution. 

krist7599555:
20161221 14:47:53
test case is weak in some case


Projjal Kundu:
20160515 17:51:24
Last edit: 20160515 17:58:03 

Kushal Saharan:
20151021 15:35:39
Getting TLE, tried to find connected graphs without bridges for every possible edge set and picked up the minimum cost set. Any suggestions how to improve this? 
Added by:  Camilo Andrés Varela León 
Date:  20070726 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  East Central North America 2005 