暂无测试数据。

Aero 国有 $n$ 座城市，编号 $0$ 到 $n-1$，每座城市 $u$ 有一个等级 $a_u$。城市之间有 $m$ 条双向道路，第 $j$ 条道路连接城市 $u_j,v_j$，长度为 $d_j$。有 $q$ 个外国旅行者来到 Aero 国旅行，第 $k$ 个旅行者要从 $s_k$ 出发前往 $t_k$，但由于护照等级 $z_k$ 的限制，他只能经过等级不超过 $z_k$ 的城市（注意起点和终点不受该条件限制，即 $s_k$ 和 $t_k$ 的等级可以大于 $z_k$，但中间经过的其它城市的等级必须小于等于 $z_k$）。对于每个旅行者，输出在此限制下的最短路径长度，若不存在满足条件的方案则输出 $-1$。

输入格式

第一行，三个正整数 $n,m,q$。

第二行，$n$ 个非负整数 $w_0,\ldots,w_{n-1}$。

接下来 $m$ 行，每行三个非负整数 $u_j,v_j,d_j$ 表示第 $j$ 条双向道路连接 $u_j,v_j$，长度为 $d_j$。可能有重边、自环。

接下来 $q$ 行，每行三个非负整数 $s_k,t_k,z_k$ 表示第 $k$ 个旅行者从 $s_k$ 到 $t_k$，护照等级为 $z_k$。

输出格式

$q$ 行，每行一个整数表示答案，如果不能到达则输出 $-1$。

数据范围

对于 $20\%$ 的数据，$n\le50$，$m\le500$，$q\le500$。

对于 $50\%$ 的数据，$n\le300$，$m\le3000$，$q\le3000$。

对于 $100\%$ 的数据，$1\le n\le 500$，$1\le m\le 100000$，$1\le q\le200000$，$0\le u_j,v_j,s_k,t_k\le n-1$，$0\le w_u,z_k\le 500$，$0\le d_j\le100$。

3 3 2
2 2 3
0 1 4
1 2 2
0 2 1
0 1 2
1 2 1

4
2