|
ACM - Universidad Autonoma de Puebla |
A Juan le gusta viajar por todo el mundo, durante sus viajes a él le gusta comprar camisetas y otros tipos de recuerdos. Dado que a Juan le sobra tiempo y le gusta gastar mucho (excepto en el transporte debido a sus malas experiencias), cada vez que desea hacer un viaje de cierto lugar a otro, elige la ruta que le cueste menos dinero, sin importarle el tiempo que requiera el viaje ni los lugares por los que pase.
Antes de hacer su viaje, Juan hace una lista de tarifas mínimas para ir de un lugar a otro, estas tarifas las obtiene de los servicios de transporte (avión, tren, autobús, etc.) a los cuales tiene alcance. Por ejemplo, si de Puebla a México en servicio de autobús le cuesta $100 y en tren $50, entonces anota en su libreta México – Puebla $50. Sin embargo esta vez esta preparando realizar un recorrido muy grande, por tal razón la lista que tarifas que hizo también lo es y necesita ayuda.
Juan te da la lista de tarifas mínimas; y a él le gustaría que le hicieras un programa que le conteste cuál es el costo mínimo para ir de cierta ciudad C1 a otra C2.
La entrada consiste de un número t (1 ≤ t ≤ 100) que indica el número de casos a procesar. Cada caso consiste de lo siguiente: en la primera línea hay dos números enteros n (1 ≤ n ≤ 100) y m (1 ≤ m ≤ 10000) donde n es el número de pueblos distintos que contiene su tabla y m el tamaño de la tabla; después siguen m líneas, cada uno con tres enteros a b c, (1 ≤ a, b ≤ n) donde a el número que representa a la ciudad origen, b el número que representa a la ciudad destino, y c (1 ≤ c ≤ 10000) el costo para ir de a a b. Después de todo lo anterior, a cada caso le continua con un número entero q que indica el número total de consultas, cada las siguientes q líneas contiene dos número ori, des, donde ori es el número que representa la ciudad origen y des el número que representa a la ciudad destino.
Para cada caso de entrada, imprime el costo mínimo de cada consulta en una línea separada, en caso de que no exista forma de llegar de ori a des imprime -1. Imprime una línea en blanco para separar la salida de cada caso de entrada. Para mayor claridad ve el ejemplo de salida.
Ejemplo de entrada |
Ejemplo de salida |
|---|---|
2 |
3 |