题目描述

疫情导致很多城市的公路都封掉了。

当疫情开始，河南省的高速公路开始慢慢恢复。

现在设河南省的城市有N个，有M条双向公路相连，每条公路有相应的长度。

现在给出第i个城市公路开通的时间t[i]。

当然如果t[i]为0，表示第i个城市就没有封锁。

现在指挥部要知道道路运行情况，有S次询问，询问格式为（st，en，q）

每个询问表示从st号城市到en城市，在第q天是否可以到达，如果可以到达，请给出最短的长度，如果不可以到达，输出-1。

输入格式

第一行包含两个正整数N，M，表示了城市的数目与公路的个数。

第二行n个整数，第i个整数表示t[i]。数据保证t[i]不下降。

接下来M行，每行三个整数st,en,w。表示st到en有一条长度为w的边。

接下来S行，每行三个整数st,en,q,表示一个询问。

数据保证S次询问，q不下降。

输出格式

S行，每行一个整数，表示答案。如题目描述

样例数据

input

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

output

-1
-1
5
4

数据规模与约定

对于30%的数据，有N≤50；

对于30%的数据，有t[i] = 0，其中有20%的数据有t[i] = 0且N＞50；

对于50%的数据，有S≤100；

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

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$