URI Online Judge | 2173

Slush Fund

By Guilherme Silva, ITA BR Brazil

Timelimit: 2

The Mayor of Nlogonia is being accused of using paving as slush fund. The investigators suspect that the mayor made a bigger budget than the one used in the paving.

In an official pronouncing, the mayor said: " I've paved the least number of streets that make possible for the citizens to travel through the city only on asphalted roads".

The NL times acquired some documents with information about the streets that could be paved and how much it would cost. This is where you enter, you were hired by NL times and received the documents they have. So you can calculate the greatest value that the politician could have stolen. Remember, you should consider that he said the truth on his speech, or he could prosecute you.


The input contains several test cases. The first line of a test case contains two integers N (1 ≤N ≤104) and M(1 ≤M ≤105), the number of corners and number of streets respectively. Each of the following M lines has three integers X (1 ≤X N), Y(1 ≤ Y N) and C(1 ≤ C ≤ 103), indicating that to pave the street from corner X to corner Y costs C.

It's always possible to choose the streets in such a way that the mayor can do his speech without lying.

After the last case, there is a line with two zeros.


For each test case you must print a line with an integer the represents how much can the mayor steal and don't lie in his speech.

Input Sample Output Sample

3 3
1 2 5
1 3 7
2 3 3
4 6
1 2 1
1 3 1
1 4 3
2 3 3
2 4 3
3 4 1
0 0