灾后重建

题目背景

$B$地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村庄的公路均无法通车。换句话说,只有连接着两个重建完成的村庄的公路才能通车,只能到达重建完成的村庄。

题目描述

给出$B$地区的村庄数$N$,村庄编号从$0$到$N-1$,和所有$M$条公路的长度,公路是双向的。并给出第$i$个村庄重建完成的时间$t_i$,你可以认为是同时开始重建并在第$t_i$天重建完成,并且在当天即可通车。若$t_i$为$0$则说明地震未对此地区造成损坏,一开始就可以通车。之后有$Q$个询问$(x, y, t)$,对于每个询问你要回答在第$t$天,从村庄$x$到村庄y的最短路径长度为多少。如果无法找到从$x$村庄到$y$村庄的路径,经过若干个已重建完成的村庄,或者村庄$x$或村庄$y$在第t天仍未重建完成 ,则需要返回$-1$。

输入输出格式

输入格式


第一行包含两个正整数$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$是不下降的。

输出格式


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

输入输出样例

输入样例 #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

说明

对于$30\%$的数据,有$N≤50$; 对于$30\%$的数据,有$t_i= 0$,其中有$20\%$的数据有$t_i = 0$且$N>50$; 对于$50\%$的数据,有$Q≤100$; 对于$100\%$的数据,有$N≤200$,$M≤N \times (N-1)/2$,$Q≤50000$,所有输入数据涉及整数均不超过$100000$。