En IslaGrande hay 
~N~ grandes lagos (numerados desde 
~1~ hasta ~N~) conectados por 
~M~ canales de los cuales se conoce su ancho. La navegación por los canales se puede realizar en ambas direcciones. Un barco puede moverse de un lago a otro si su ancho es menor o igual al ancho del canal que conecta los dos lagos.
Como consecuencia del desarrollo económico de esta región la compañía está interesada en transportar más personas y mercancías en cada viaje que en usar la vía más corta, por lo que desean realizar cada transportación con el barco más ancho posible aunque esto implique viajar por una ruta más larga.
Tarea
Hacer un programa que permita:
- Leer la cantidad de lagos, canales y transportaciones entre los lagos, además de la información de cada canal y los lagos entre los cuales se realizarán las transportaciones.
- Encontrar el máximo ancho de cada uno de los barcos que navegarán entre cada par de lagos de las
~K~ transportaciones a realizar.
- La salida ~K~ líneas, cada una conteniendo un entero, el cual representa el máximo ancho del barco que viajará entre los dos lagos correspondientes en la entrada.
Entrada
La entrada contiene:
- Línea 1:
~N, M~ y ~K~, separados entre sí por un espacio en blanco, los cuales representan la cantidad de lagos, canales y transportaciones a realizar entre los lagos.
- Línea 2..N+1:
~i, j~ y 
~w~, separados entre sí por un espacio en blanco, los cuales indican que existe un canal entre los lagos 
~i~ y 
~j (1 \leq i, j \leq N)~ con un ancho ~w~.
- Línea N+2..N+K+3: cada una conteniendo dos enteros, los números de los lagos entre los cuales el barco debe viajar.
Salida
La salida tendrá ~K~ filas, cada una conteniendo un entero, el cual representa el máximo ancho del barco que viajará entre los dos lagos correspondientes en la entrada.
Restricciones
~2 \leq N \leq 1 000~.
~1 \leq M \leq 100 000~.
~1 \leq K \leq 10 000~.
~1 \leq Wi,j \leq 200~.
Ejemplo de Entrada
6 9 4
1 2 2
1 4 3
1 6 1
2 3 3
2 5 2
3 4 4
3 6 2
4 5 5
5 6 4
2 6
3 5
1 2
4 6
Ejemplo de Salida
3
4
3
4
Comments