City in the Center
By Hamilton José Brumatto, UESC 
Brazil
By Hamilton José Brumatto, UESC Brazil
Your colleague, a peddler, has a cartel of clients in a set of cities linked by highways. He needs to choose a city to live in. What he wants is for the city to be approximately in the center of the set. He asked you to indicate which city is in the center. The city is said to be located in the center, if the sum of the distance of this to all the others is the minimum possible. The highways that connect the cities do not have crossroads, they are only intersected in the cities themselves. And it is guaranteed that all cities are reached from any other using one or a set of roads.
The input is composed of several test cases. Each test case starts with two positive integer values: N and R, where 0 < N ≤ 100 the number of cities, and 0 ≤ R ≤ 4950 the number of highways that interconnect cities. Next are R rows containing three positive integer values: A, B, and D, separated by a blank space each. A and B are two distinct cities 0 < A ≠ B ≤ N. Cities are numbered from 1 to N inclusive. D is the distance between A and B through a road linking both, 0 < D <1,000. The test cases end with N = R = 0.
For each test case the number of the "City in the center" should be printed on the output. If there is more than one city in these conditions, all must be listed, in ascending order of the city number. There will always be a single space after each city number, including the last one.
| Input Sample | Output Sample |
|
4 6 |
4 |