F. Yuhina City
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
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$$$。

Input

第一行，一个整数 $$$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$$$ 的总和没有额外约束。

Output

对于每次询问，输出一行整数，代表在这次运输救灾物资的过程中，需要承受的辐射的最小值。

Example
Input
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
Output
10
1
0
0
0
8
8
11
15