Let us commemorate our greatest comrade, Yuhina.
Yuhina City 是一个 n 个点 m 条边的无向连通图。
现在有一些含有辐射的废料在城市的一些节点处泄露了，废料的辐射值会随着距离递减，即假如节点 i 有一个辐射值为 ri 的废料，那么假如节点 j 和节点 i 的最短距离为 d，那么节点 j 的辐射值为 max(0,ri−d)。假如一个点被多个废料影响，那么这个点的辐射值取最高的那个。
作为 Yuhina，你需要把救灾物资从节点 u 送到另一个节点 v，同时你有一件抗辐射服，最多可以抵挡 k 次你在某个节点受到的辐射，那么你需要承受的辐射的最小值是多少。
即假如有一条从 u 到 v 的路径，经过的节点的辐射值为 ru,ra,rb,…,rv，并且你的抗辐射服可以抵挡 k 次你在某个节点受到的辐射，那么将这些节点的辐射值从大到小排序后，你需要承受的辐射值为其中第 k+1 大的数字。假如这条路径上经过的节点数小于等于 k 个，那么你需要承受的辐射值就是 0。
第一行，一个整数 t(1≤t≤104)，代表数据组数。
对于每组数据：
第一行，三个整数 n,m,q(2≤n≤105;n−1≤m≤2⋅105;1≤q≤5)，代表 Yuhina City 的节点数、连接这些节点的边数和你需要运送救灾物资的次数。
第二行，n 个整数 r1,…,rn(0≤ri≤1014)，代表每个点泄露的核废料的辐射值，假如 ri=0，代表这个点没有核废料泄露。
接下来的 m 行，每行三个整数 u,v,w(1≤u,v≤n,u=v;1≤w≤109)，代表节点 u 和 v 被一条长度为 w 的无向边连接。
接下来的 q 行，每行三个整数 u,v,k(1≤u,v≤n,u=v;0≤k≤n)，代表运送物资的起点和终点以及抗辐射服可以最多抵挡的辐射次数。
保证同一测试点 n 的总和不超过 105 且 m 的总和不超过 2⋅105。对于 q 的总和没有额外约束。
对于每次询问，输出一行整数，代表在这次运输救灾物资的过程中，需要承受的辐射的最小值。
输入样例
2
3 2 4
0 10 0
1 2 9
2 3 10
1 3 0
1 3 1
1 3 2
1 3 3
6 10 5
5 0 11 15 11 0
2 1 8
3 1 3
3 4 1
5 1 3
6 2 1
2 6 3
6 5 4
3 2 6
4 6 9
1 6 4
2 1 3
5 2 1
2 4 1
1 6 0
3 4 0
输出样例
10
1
0
0
0
8
8
11
15