Todos los años se realiza en la Isla Stuart, la Feria Tecnológica para Hámster (FTH) más importante del año. Como en cada año, se muestra en cada una de las ~N\,(1 \leq N \leq 250)~ salas de exposiciones (convenientemente enumeradas ~1...N~), todo lo relacionado con ruedas, escaleras y otros artículos que hacen la vida más feliz a estos animalitos. Las salas están conectadas por ~M\,(1 \leq M \leq 25\,000)~ pasillos de una dirección (convenientemente enumerados de ~1...M~), donde el pasillo ~i~ permite el paso de la sala ~S_i~ a la ~E_i~ y no de ~E_i~ a ~S_i~, y es posible atravesarlo si se tiene un pase de acceso con valor ~H\,(1 \leq H \leq 1000\,000)~ igual o mayor al del pasillo. Para que la FTH sea más interesante es necesario completar ~T\,(1 \leq T \leq 40\,000)~ tareas. La tarea ~i~ comprende dos números diferentes; ~A_i~ y ~B_i~ (~1 \leq A_i \leq N; 1 \leq B_i \leq N~), que denotan que un hámster tiene que viajar de la sala ~A_i~ a la sala ~B_i~ (recorriendo uno o más pasillos a través de alguna ruta). El precio de un pase de acceso es equivalente al valor del mismo, en otras palabras un pase de acceso con precio 5 pesos es válido para atravesar cualquier pasillo de valor menor o igual a 5.

Ponyo es un hámster amante a la tecnología, por lo que quiere completar las ~T~ tareas. Ser amante de la tecnología no significa que tengas mucho dinero, por lo que Ponyo quiere completar las ~T~ tareas de la manera más económica posible.

Usted debe hacer un programa que determine para cada tarea el precio del menor pase de acceso que debe comprar que le permita desplazarse de la Sala ~A_i~ a la ~B_i~.

Entrada

• Línea 1: Tres enteros separados por espacios: ~N, M~ y ~T~.
• Líneas 2..M+1: La línea ~i+1~ contiene tres enteros separados por espacios: ~S_i, E_i~ y ~H_i~; que significa que entre la sala ~S_i~ y la sala ~E_i~ hay um pasillo de valor ~H_i~;
• Líneas M+2..M+T+1: La línea ~i+M+1~ contiene dos enteros separados por espacio que describen la tarea ~i~: ~A_i~ y ~B_i~.

Salida

Líneas 1...T: La línea ~i~ contiene el resultado de la tarea ~i~ y dice el posible menor precio de un pase necesario para ir entre las salas dadas. Dé como salida –1 si es imposible viajar entre las dos salas.

Ejemplo de entrada

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1

Ejemplo de salida

4
8
-1

Detalles de la salida

Pregunta #1: La mejor manera es simplemente viajar en el camino de la sala 3 a la sala 4. Pregunta #2: Hay un camino de la sala 1 a la sala 2, pero una mejor manera sería viajar de la sala 1 a la sala 3 y luego a la sala 2. Pregunta #3: No hay caminos que comiencen en la sala 5, por lo tanto es claro que no hay manera de llegar a la sala 1 desde la sala 5.