El profesor de música
En las últimas décadas, las zonas rurales han ido perdiendo cada vez más habitantes que han emigrado a las grandes ciudades. Eso ha hecho que el número de niños en los pueblos haya disminuido hasta tal punto que muchas veces no es económicamente viable tener un colegio en cada pueblo y, mucho menos, un profesor especialista en cada uno de ellos.
Es por eso que muchos profesores de esas zonas rurales tienen asignados varios pueblos y a lo largo del día tienen que pasar por todos ellos para ilustrar las mentes en blanco de los chavales.
El profesor de música lleva años en esa situación. Cada año le asignan hasta 6 pueblos distintos que tiene que visitar obligatoriamente todos los días. Afortunadamente los horarios de sus clases los puede configurar a voluntad para poder recorrerlos en el orden que minimice el número de kilómetros que hace.
Después de darle muchas vueltas a la cabeza y harto de pasarse horas y horas en la carretera, ha decidido vivir de alquiler. Cada año, una vez que conozca los pueblos donde tiene que ir, decidirá a qué pueblo irse a vivir y en qué orden visitar los colegios. Pero no tiene ni idea de cómo va a hacer esa selección. La información de carreteras es fácil de conseguir en forma de tablas de los segmentos de carretera entre las distintas poblaciones y la distancia entre ellas. Lo que es más difícil es averiguar qué pueblo minimiza el número de kilómetros diarios que tiene que hacer. Sobre todo porque en ningún caso se mudará al pueblo de uno de los colegios, para no encontrarse con sus alumnos cuando vaya a comprar el pan.
Entrada
La entrada está formada por distintos casos de prueba, cada uno representando la información de carreteras de una comarca y varios años en la vida del profesor en donde los pueblos asignados cambian.
Cada caso de prueba comienza con una línea con dos números, np y nc con el número de pueblos de la comarca (2 ≤ np ≤ 2.000) y el número de carreteras en la comarca (nc ≤ 25.000).
Tras eso, vendrán nc líneas con la información de carreteras, que se componen de dos números indicando los pueblos que unen (entre 1 y np) y los kilómetros que las separan. Ten en cuenta que puede haber carreteras con los mismos pueblos de origen y destino y que, incluso, puede haber carreteras rurales que comiencen y terminen en el mismo pueblo (útiles para que los agricultores hagan la ronda por sus tierras).
A continuación vendrá un número c indicando el número de cursos distintos por los que se pregunta (como mucho 100). Las c líneas siguientes contienen la información de la asignación de pueblos de ese curso: el número de pueblos asignados (entre 1 y 6) y los identificadores de cada pueblo.
Salida
Por cada caso de prueba se escribirá una línea por cada curso impartido en esa comarca. Cada línea contendrá dos números: el identificador del pueblo donde mudarse y los kilómetros recorridos en el coche diariamente.
Se garantiza que siempre habrá solución. Si hay más de un pueblo que minimice la distancia recorrida, se elegirá el pueblo con menor identificador (los pueblos con menor identificador tienen alquileres más baratos).
Después de cada caso de prueba vendrá una línea con tres guiones (---).
Entrada de ejemplo
2 1 1 2 1 1 1 1 4 5 1 2 1 1 3 1 1 4 1 2 3 1 2 4 1 2 2 1 2 3 4 1 2
Salida de ejemplo
2 2 --- 3 3 3 4 ---