The goal of the provincial government's "unobstructed project" is to enable road traffic between any two villages in the province (but not necessarily directly connected by roads, as long as it can be reached indirectly by roads). After investigation and evaluation, the cost of several possible roads is listed in the statistical table. Love the country's 1023, eager to respond to the call of the state, even if their strength is not good, but he has money. Please be his accountant. Now you are writing a program to calculate the minimum cost for the smooth flow of the whole province.

The test input contains several test cases. The first row of each test case gives the estimated number of roads N, the number of villages M (< 100), and the subsequent N

Rows correspond to the cost of roads between villages. Each row gives a pair of positive integers, the number of two villages, and the cost of roads between the two villages (also positive integers). For simplicity, villages are numbered from 1 to M. When N is 0, all input ends, and the corresponding results do not output

For each test case, output the lowest cost required by the whole province in 1 rows. 1023 promise the graph is connection.