Itinerary of Santa Claus
By Neilor Tonin, beecrowd 
Brazil
By Neilor Tonin, beecrowd Brazil
Before Santa Claus begin his travels in Brazil to deliver Christmas presents, he asked you to help him drawing a map with all the cities that he should visit. Follows the rule to draw this map: the sum of all routes (distances between two cities) existing on the map should be as small as possible and must be possible to arrive in any destination from any origin. Claus does not mind to go to a particular city more than once, as long as it uses only the routes drawn on the map.
The input file contains several test cases. Each test case starts with two numbers M (2 ≤ M < 40000) and N (1 ≤ N < 50000), the number of cities and the number of roads respectively. Input is terminated by M = N = 0. Then follow N integer triples X (0 ≤ X), Y (Y < M) and Z (1 ≤ Z ≤ 999), pecifying that there will be a bidirectional route between X and Y with Z kilometers, considering that X ≠ Y and the total sum of all routes in each map is less than 231.
For each test case, print a single integer indicating the sum of all distances or routes of your map.
| Input Sample | Output Sample |
|
6 8 |
1140 |