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, \ldots, t_{N-1} ，表示了每个村庄重建完成的时间。数据保证了 t_0 \leq t_1 \leq \cdots \leq t_{N-1} 。
• 接下来 M 行，每行包含 3 个非负整数 i, j, w ， w 不超过 10000，表示有一条连接村庄 i 与村庄 j 的道路，长度为 w 。保证 i \neq j ，且对于任意一对村庄只存在一条道路。
• 接下来一行包含一个正整数 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。

提示

• 对于 30% 的数据，有 N \leq 50 ；
• 对于 30% 的数据，有 t_i = 0 ，其中有 20% 的数据有 t_i = 0 且 N > 50 ；
• 对于 50% 的数据，有 Q \leq 100 ；
• 对于 100% 的数据，有 1 \leq N \leq 200 ， 0 \leq M \leq \frac{N \times (N - 1)}{2} ， 1 \leq Q \leq 50000 ，所有输入数据涉及整数均不超过 10^5 。

floyd