#558. Yuhina City

Let us commemorate our greatest comrade, Yuhina.

Yuhina City 是一个 $n$ 个点 $m$ 条边的无向连通图。

现在有一些含有辐射的废料在城市的一些节点处泄露了，废料的辐射值会随着距离递减，即假如节点 $i$ 有一个辐射值为 $r_i$ 的废料，那么假如节点 $j$ 和节点 $i$ 的最短距离为 $d$，那么节点 $j$ 的辐射值为 $\max(0,r_i-d)$。假如一个点被多个废料影响，那么这个点的辐射值取最高的那个。

作为 Yuhina，你需要把救灾物资从节点 $u$ 送到另一个节点 $v$，同时你有一件抗辐射服，最多可以抵挡 $k$ 次你在某个节点受到的辐射，那么你需要承受的辐射的最小值是多少。

即假如有一条从 $u$ 到 $v$ 的路径，经过的节点的辐射值为 $r_u,r_a,r_b,\dots,r_v$，并且你的抗辐射服可以抵挡 $k$ 次你在某个节点受到的辐射，那么将这些节点的辐射值从大到小排序后，你需要承受的辐射值为其中第 $k+1$ 大的数字。假如这条路径上经过的节点数小于等于 $k$ 个，那么你需要承受的辐射值就是 $0$。

第一行，一个整数 $t(1\le t\le 10^4)$，代表数据组数。

对于每组数据：

第一行，三个整数 $n,m,q(2\le n\le 10^5;n-1\le m\le 2\cdot 10^5;1\le q\le 5)$，代表 Yuhina City 的节点数、连接这些节点的边数和你需要运送救灾物资的次数。

第二行，$n$ 个整数 $r_1,\dots,r_n(0\le r_i\le 10^{14})$，代表每个点泄露的核废料的辐射值，假如 $r_i=0$，代表这个点没有核废料泄露。

接下来的 $m$ 行，每行三个整数 $u,v,w(1\le u,v\le n,u\neq v;1\le w\le 10^9)$，代表节点 $u$ 和 $v$ 被一条长度为 $w$ 的无向边连接。

接下来的 $q$ 行，每行三个整数 $u,v,k(1\le u,v\le n,u\neq v;0\le k\le n)$，代表运送物资的起点和终点以及抗辐射服可以最多抵挡的辐射次数。

保证同一测试点 $n$ 的总和不超过 $10^5$ 且 $m$ 的总和不超过 $2\cdot 10^5$。对于 $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