疫后开放

Background

L同学周末很喜欢去找别的同学贴贴，但是A 地区在疫情过后，所有小区都进行了静止，在小区开放之前，所有与静止的小区的公路均无法通车。换句话说，只有连接着两个开放的小区的公路才能通车，只能到达开放的小区。

Description

给出 A 地区的小区数 $N$，小区编号从 $0$ 到 $N-1$，和所有 $M$ 条公路的长度，公路是双向的。并给出第 $i$ 个小区开放的时间 $t_i$。之后有 $Q$ 个询问 $(x,y,t)$，对于每个询问你要回答在第 $t$ 天，从小区 $x$ 到小区 $y$ 的最短路径长度为多少。如果无法找到从 $x$ 小区到 $y$ 小区的路径，或者小区 $x$ 或小区 $y$ 在第 $t$ 天仍未重建完成，则需要返回 -1。

Input

第一行包含两个正整数$N,M$，表示了小区的数目与公路的数量。

第二行包含$N$个非负整数$t_0, t_1,…, t_{N-1}$，表示了每个村庄重建完成的时间，数据保证了$t_0 ≤ t_1 ≤ … ≤ t_{N-1}$。

接下来$M$行，每行$3$个非负整数$i, j, w$，$w≤10000$，表示了有一条连接村庄$i$与村庄$j$的道路，长度为$w$，保证$i≠j$，且对于任意一对村庄只会存在一条道路。

接下来一行也就是$M+3$行包含一个正整数$Q$，表示$Q$个询问。

接下来$Q$行，每行$3$个非负整数$x, y, t$，询问在第$t$天，从小区$x$到小区$y$的最短路径长度为多少，数据保证了$t$是不下降的。

Output

共$Q$行，对每一个询问$(x, y, t)$输出对应的答案，即在第$t$天，从小区$x$到小区$y$的最短路径长度为多少。如果在第t天无法找到从$x$村庄到$y$村庄的路径，经过若干个已重建完成的小区，或者小区x或小区$y$在第$t$天仍未修复完成，则输出$-1$。

Samples

输入数据 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
-1
5
4

提示

对于$100\%$的数据，有$N≤200$，$M≤N \times (N-1)/2$，$Q≤50000$，所有输入数据涉及整数均不超过$100000$。