Hay ~n~ ciudades y ~m~ carreteras entre ellas. Su tarea consiste en procesar ~q~ consultas en las que debe determinar la longitud de la ruta más corta entre dos ciudades dadas.

Entrada

La primera línea de entrada tiene tres enteros ~n, m~ y ~q~: el número de ciudades, carreteras y consultas. A continuación, hay ~m~ líneas que describen las carreteras. Cada línea tiene tres enteros ~a, b~ y ~c~: hay una carretera entre las ciudades ~a~ y ~b~ cuya longitud es ~c~. Todas las carreteras son de doble sentido. Por último, hay ~q~ líneas que describen las consultas. Cada línea tiene dos enteros ~a~ y ~b~: determinar la longitud de la ruta más corta entre las ciudades ~a~ y ~b~.

Salida

Imprime la longitud de la ruta más corta para cada consulta. Si no hay ruta, imprime ~-1~.

Restricciones

• ~1 \leq n \leq 500~.
• ~1 \leq m \leq n^2~.
• ~1 \leq q \leq 10^5~.
• ~1 \leq a, b \leq n~.
• ~1 \leq c \leq 10^9~.

Ejemplo de Entrada

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

Ejemplo de Salida

5
5
8
-1
3