题目背景

地震损坏了 B 地区的村庄，公路本身完好。重建期间，任何一端尚未修复的道路都不能通行。只有两端的村庄均完成重建，道路才会开放，行程中也只能经过已恢复的村庄。

题目描述

B 地区的 $N$ 个村庄编号为 $0$ 到 $N-1$，有 $M$ 条双向公路。所有村庄同时开始重建，村庄 $i$ 在第 $t_i$ 天重建完成，当天即可通行。若 $t_i=0$，表示该村庄没有受损，从一开始就能通行。

现在给出各村庄的重建时间和所有公路的长度，再给出 $Q$ 个询问 $(x,y,t)$。对每个询问，求第 $t$ 天从村庄 $x$ 前往村庄 $y$ 的最短路程。起点、终点和沿途经过的每个村庄都必须在当天或此前完成重建。若端点仍未开放，或这些已开放的村庄间没有可行路线，输出 $-1$。

输入格式

第一行给出村庄数 $N$ 与公路数 $M$。第二行给出 $N$ 个非负整数 $t_0,t_1,\ldots,t_{N-1}$，按编号列出村庄重建完成的日期，且 $t_0\le t_1\le\cdots\le t_{N-1}$。

随后 $M$ 行各含三个非负整数 $i,j,w$，表示村庄 $i$ 与 $j$ 间有一条长度为 $w$ 的公路。保证 $i\ne j$、$w\le10000$，且任意两个村庄之间至多有一条公路。

第 $M+3$ 行是正整数 $Q$。再往下的 $Q$ 行，每行用三个非负整数 $x,y,t$ 表示一次询问，即第 $t$ 天从 $x$ 前往 $y$ 的最短距离。各次询问按时间非递减的顺序给出。

输出格式

共输出 $Q$ 行，依次回答各个询问。对于 $(x,y,t)$，若 $x$ 或 $y$ 到第 $t$ 天仍未恢复，或当天无法从 $x$ 沿已恢复村庄到达 $y$，输出 $-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

说明/提示

原题的分档数据范围如下。