Dosberto después de revisar los recibos de su viaje en automóvil por Europa este verano, se dio cuenta de que los precios de la gasolina variaban entre las ciudades que visitaba. ¿Quizás podría haber ahorrado algo de dinero si fuera un poco más inteligente acerca de dónde llenó el combustible? Para ayudar a otros turistas (y ahorrar dinero la próxima vez), desea escribir un programa para encontrar la forma más barata de viajar entre ciudades, llenando su tanque en el camino. Suponemos que todos los automóviles usan una unidad de combustible por unidad de distancia y comienzan con un tanque de gasolina vacío.

Entrada

La primera línea de entrada contiene a $1\le N\le 1000$ y $0\le M\le 10000$, el número de ciudades y carreteras. Luego sigue una línea con $N$ números enteros $1\le Pi\le 100$, donde $Pi$ es el precio de una unidad de combustible en la i-ésima ciudad. Luego siguen $M$ líneas con tres números enteros $0\le U,V<N$ y $1\le D\le 100$, indicando que hay una carretera entre $U$ y $V$ con longitud $D$. Luego viene una línea con el número $1\le Q\le 100$, dando el número de consultas, y $Q$ líneas con tres enteros $1\le C\le 100$, $S$ y $E$, donde $C$ es la capacidad de combustible del vehículo, $S$ es la ciudad de partida , y $E$ es la ciudad a la que se quiere llegar.

Salida

Para cada consulta, genere el precio del viaje más barato de $S$ a $E$ usando un automóvil con la capacidad dada, o "impossible" si no hay forma de ir de $S$ a $E$ con el automóvil dado.

Ejemplo de Entrada

5 5
10 10 20 12 13 
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

Ejemplo de Salida

170
impossible