Reconstruction

Problem Description

After the earthquake in region $B$, all villages suffered some damage, but the earthquake had little effect on the roads. However, before a village is rebuilt, none of the roads connected to an unrebuilt village can be used. In other words, only roads connecting two rebuilt villages can be used, and one can only reach rebuilt villages.

You are given the number of villages $N$ in region $B$ (villages are numbered $0$ to $N - 1$) and the lengths of all $M$ bidirectional roads. You are also given the reconstruction completion time $t_i$ of the $i$-th village; you may assume all villages start rebuilding simultaneously and are completed on day $t_i$, and can be used for traffic on that same day. If $t_i$ is $0$, it means the earthquake caused no damage to this region and it can be used from the very beginning.

Then there are $Q$ queries $(x, y, t)$. For each query you must answer: on day $t$, what is the length of the shortest path from village $x$ to village $y$? If, going through some already-rebuilt villages, no path from village $x$ to village $y$ can be found, or if village $x$ or village $y$ is not yet rebuilt by day $t$, then return $-1$.

Input Format

The first line contains two positive integers $N, M$, the number of villages and the number of roads.

The second line contains $N$ non-negative integers $t_0, t_1, \dots, t_{N-1}$, the reconstruction completion times of each village. The data guarantees $t_0 \leq t_1 \leq \dots \leq t_{N-1}$.

The next $M$ lines each contain $3$ non-negative integers $i, j, w$, where $w$ is a positive integer not exceeding $10000$, meaning there is a road of length $w$ connecting villages $i$ and $j$. It is guaranteed that $i \neq j$, and that for any pair of villages there is at most one road.

The next line (that is, line $M + 3$) contains a positive integer $Q$, the number of queries.

The next $Q$ lines each contain $3$ non-negative integers $x, y, t$, asking for the length of the shortest path from village $x$ to village $y$ on day $t$. The data guarantees that $t$ is non-decreasing.

Output Format

Output $Q$ lines in total. For each query $(x, y, t)$, output the corresponding answer — the length of the shortest path from village $x$ to village $y$ on day $t$. If on day $t$ no path from village $x$ to village $y$ can be found, or village $x$ or village $y$ is not yet rebuilt, output $-1$.

Sample Input

4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4

Sample Output

-1
-1
5
4

Constraints

$N \leq 200$, $M \leq N \times (N - 1) / 2$, $Q \leq 50000$; all integers involved in the input do not exceed $100000$.