Description

Given the number of villages $N$ in Region B, numbered from $0$ to $N-1$, and the lengths of all $M$ bidirectional roads. For each village $i$, you are given the day it is completed $t_i$. All reconstructions start simultaneously, and village $i$ is completed on day $t_i$, becoming open to traffic on that day. If $t_i$ is $0$, the earthquake did not damage that village and it is open from the beginning. Then there are $Q$ queries $(x,y,t)$. For each query, answer the length of the shortest path from village $x$ to village $y$ on day $t$. If there is no path from $x$ to $y$ using only villages that have been completed by day $t$, or if village $x$ or village $y$ has not been completed by day $t$, output $-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,\cdots,t_{N-1}$, the completion day of each village, and it is guaranteed that $t_0 \le t_1 \le \cdots \le t_{N-1}$.
• The next $M$ lines each contain three non-negative integers $i,j,w$ with $w \le 10000$, indicating a road between villages $i$ and $j$ with length $w$. It is guaranteed that $i \ne j$, and for any pair of villages there is at most one road.
• The next line contains a positive integer $Q$, the number of queries.
• The next $Q$ lines each contain three non-negative integers $x,y,t$, asking for the shortest path length from village $x$ to village $y$ on day $t$. It is guaranteed that $t$ is non-decreasing across the queries.

Output Format

Output $Q$ lines. 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$ there is no path from $x$ to $y$ using only villages that have been completed by day $t$, or if village $x$ or village $y$ has not been completed by day $t$, output $-1$.

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

-1
-1
5
4

Hint

• For $30\%$ of the testdata, $N \le 50$.
• For $30\%$ of the testdata, $t_i=0$; among them, for $20\%$ of the testdata, $t_i=0$ and $N>50$.
• For $50\%$ of the testdata, $Q \le 100$.
• For $100\%$ of the testdata, $1 \le N \le 200$, $0 \le M \le \dfrac{N\times(N-1)}{2}$, $1 \le Q \le 50000$, and all integers in the input are at most $10^5$.

Translated by ChatGPT 5