¿Cuál es el mejor camino?
Hace poco me he mudado a una nueva ciudad. Aprovechando que me gusta caminar, siempre que puedo voy andando a los sitios y así la voy conociendo. Cuando voy lejos y tengo prisa suelo coger las grandes avenidas porque las conozco más y sé que no voy a perderme, pero soy consciente de que, muchas veces, callejeando por calles cortas recorrería menos distancia, aunque tuviese que atravesar muchas de ellas. Me pregunto cómo de habitual es que el camino más corto en distancia sea también el que pasa por menos calles.
Como ejemplo, el siguiente esquema representa una ciudad con siete intersecciones y ocho calles donde junto a cada calle aparece su longitud (un valor siempre entero). Para ir del punto 1 al punto 5 el camino más corto es el 1 → 2 → 3 → 5 con una longitud de 27 y atravesando tres calles, mientras que el camino 1 → 4 → 5, aunque es más largo (mide 30), pasa solamente por dos calles. En cambio, el camino más corto que une los puntos 6 y 5 sí utiliza el menor número de calles (no hay ningún otro camino con menos calles).
Entrada
La entrada consta de varios casos de prueba, ocupando cada uno de ellos varias líneas.
En la primera aparece el número N (entre 2 y 20.000) de intersecciones en la ciudad, y en la segunda el número C (entre 0 y 100.000) de calles (entre intersecciones). A continuación, aparece una línea por cada calle con tres enteros, que indican los números de las intersecciones que une la calle (números entre 1 y N) y su longitud (un valor entre 1 y 5.000). Todas las calles pueden recorrerse en ambos sentidos.
A continuación aparece el número K (entre 1 y 10) de consultas seguido de esas consultas: dos números distintos que representan las intersecciones origen y destino.
Salida
Para cada caso de prueba se escribirá una línea por cada consulta que contendrá la distancia mínima que hace falta recorrer para ir desde el origen al destino, seguida de la palabra SI si es posible recorrer esa distancia utilizando el menor número de calles o NO en caso contrario. Si para una consulta no existiera camino que conecte el origen con el destino, entonces se escribiría SIN CAMINO.
Después de la salida de cada caso se escribirá una línea con ----.
Entrada de ejemplo
7 8 1 2 10 2 3 7 3 5 10 1 4 15 4 5 15 4 6 5 5 7 4 6 7 15 2 1 5 6 5 5 4 1 2 5 2 3 5 3 1 5 4 5 10 2 1 2 1 5
Salida de ejemplo
27 NO 19 SI ---- 5 SI SIN CAMINO ----