Calax Research and Development is a large high tech corporation. They have an antitrust lawsuit on their hands because they are too big. The judge has ordered that the corporation be split into two new companies, A and B. Calax has a large network of communication lines that connect a number of cities (each city is connected to every other city by a path of communication lines). They now need to split those lines into two sets, A and B. It is important that each of the two sets still connects all of the cities because the two companies will not be allowed to share communication lines. It has also been decided that all redundant lines will be sold off to protect the two new companies from more antitrust lawsuits. And of course, the total cost of this operation needs to be as small as possible. Input The input will contain a number of cases. Each case will begin with n — the number of cities (at most 10), followed by m — the number of communication lines (at most 25). The next m lines will contain 3 numbers each - the two cities connected by the line and the cost of keeping the line. Each city will be identified by an integer in the range [1,n]. The cost of a line is at most 1000. The input will be terminated by the case where n is zero. Output Output one integer per test case on a line by itself — the minimum total cost of the communication lines in sets A and B. Print ‘No way!’ if there is no solution. Comments In the third test case, one possible solution is to let company A keep these communication lines: 1 2 10 1 3 10 1 4 10 1 5 20 and let company B keep these ones: 1 4 20 2 3 20 3 4 20 4 5 30 for a total cost of 50 + 90 = 140. Xander: “Calax Research and Development. It’s a computer research lab. Third largest employer in Sunnydale till it closed down last year. What, I can’t have information sometimes?” Giles: “Well, it-it’s just somewhat unprecedented.” Ashley Gable and Thomas A. Swyden, "Buffy the Vampire Slayer."
2/2 Sample Input 2 3 1 2 10 2 1 20 1 2 30 3 3 1 2 10 1 2 20 2 3 50 5 8 1 2 10 1 3 10 1 4 10 1 4 20 1 5 20 2 3 20 3 4 20 4 5 30 0 Sample Output 30 No way! 140