RapidEats
Rocky Rutanator trabaja como planificador de rutas para la empresa RapidEats, un servicio de entrega de alimentos a domicilio que opera en la bulliciosa ciudad de Deliciaville.
RapidEats tiene varias sedes, y utiliza para el reparto unas motillos eléctricas con poca autonomía. Por ello es importante que Rocky proporcione a cada uno de los repartidores instrucciones precisas sobre la ruta que tiene que seguir para ahorrar batería.
Afortunadamente, cuenta con información detallada de la ciudad, vista como una red de puntos conectados por una intrincada red de tramos de calles, cada uno con una duración estimada para recorrerlo.
¿Cuál es el tiempo mínimo requerido para llevar un pedido desde el punto de partida P hasta el punto de entrega final Q a través de una secuencia de tramos?
Entrada
La entrada consta de varios casos de prueba, ocupando cada uno de ellos varias líneas.
En la primera aparecen, separados por un espacio, el número N de puntos de la red (entre 2 y 20.000) y el número C de tramos de calles que los unen (entre 0 y 100.000). A continuación, aparece una línea por cada tramo con tres enteros, que indican los números de los puntos que une ese tramo (números entre 1 y N) y el tiempo estimado para recorrerlo (un valor entre 1 y 500). Todas las calles pueden recorrerse en ambos sentidos.
A continuación aparece el número K (entre 1 y 10) de pedidos a repartir seguido de la información de esos pedidos: dos números distintos que representan el punto de origen y el de destino de cada pedido.
Salida
Para cada caso de prueba se escribirá una línea por cada pedido que contendrá el tiempo mínimo para ir desde el origen al destino. Si para un pedido no existiera camino que conectara el origen con el destino, entonces se debe escribir NO LLEGA.
Después de la salida de cada caso se escribirá una línea con ---.
Entrada de ejemplo
4 4 1 2 15 1 3 30 2 3 20 4 3 10 2 1 3 4 1 4 2 1 3 10 2 4 20 2 1 2 3 1
Salida de ejemplo
30 40 --- NO LLEGA 10 ---