2023年5月2日23时27分在云南保山市隆阳区发生5.2级地震，地震过后对村庄、城市等都造成了一定的损毁，现在需要对受灾地区进行灾后重建工作。
村庄之间的公路为双向车道且完好无损，只有村庄受到损毁。每个村庄受损程度不一样，因此重建时间也不相同，所有受损村庄都从0时刻开始重建。某地区共有n个村庄，村庄之间共有m条长度不一的公路。村庄从0到 n-1编号，第i个村庄重建完成的时间为t_i。若t_i = 0 则说明此村庄未受损。
给定q个询问（x,y,d），对于每个询问，你要回答在第d天，从村庄x到村庄y的最短路径长度为多少。只有重建完成的村庄才可到达或者作为中转站点。如果无法在第d天找到从村庄x到村庄y的路径，则返回-1。

第一行包含两个正整数n和m，表示村庄的数目和公路的条数。
第二行包含n个非负整数t_0⋯⋯t_(n-1),分别表示第0个到第n-1个村庄重建所需时间。需注意，重建时间不一定从小到大。
接下来m行，每行3个非负整数(i，j，w),w为不超过1000的正整数，表示村庄i与村庄j (i!=j)有一条长度为w的道路。
第m+3行为一个正整数q，表示有q个询问。接下来的q行，每行3个非负整数(x，y，d)，询问在第d天，从村庄x到村庄y的最短路径长度为多少，且每增加一次询问，重建时间递增。
数据范围
对于 20% 的数据，n≤200，m≤100。
对于 100% 的数据，n≤200,m≤10^4。

共q行，对每一个询问(x，y，d) 输出对应的答案。<br>