Cidade no Centro
Por Hamilton José Brumatto, UESC 
Brazil
Por Hamilton José Brumatto, UESC Brazil
Seu colega, vendedor mascate, possui um cartel de clientes em um conjunto de cidades interligadas por rodovias. Ele precisa escolher uma cidade para morar. O que ele quer é que a cidade fique aproximadamente no centro do conjunto. Ele pediu a você que indique qual a cidade que fica no centro. A cidade é dita localizar-se no centro, se a soma da distância desta para todas as demais é a mínima possível. As rodovias que interligam as cidades não possuem cruzamentos, somente se encontram nas cidades em si. E é garantido que todas as cidades são atingíveis a partir de qualquer outra usando uma ou um conjunto de estradas.
A entrada é composta de vários casos de teste. Cada caso de teste inicia com dois valores inteiros positivos: N e R, onde 0 < N ≤ 100 o número de cidades, e 0 ≤ R ≤ 4950 o número de rodovias que interligam as cidades. Em seguida são R linhas contendo três valores inteiros positivos: A, B e D, separados por um espaço em branco cada. A e B são duas cidades distintas 0 < A ≠ B ≤ N. As N cidades são numeradas de 1 a N inclusive. D é a distância entre A e B através de uma estrada que liga ambas, 0 < D < 1.000. Os casos de teste terminam com N = R = 0.
Para cada caso de teste deve ser impresso na saída o número da "Cidade que fica no centro". Se houver mais de uma cidade nestas condições, devem ser listadas todas, em ordem crescente do número da cidade. Sempre haverá um único espaço em branco após cada número de cidade, inclusive da última.
| Exemplo de Entrada | Exemplo de Saída |
|
4 6 |
4 |