【题目描述】

qo 感觉自己太弱了，于是准备去很远的地方进修，让自己变得更强。

qo 准备来到第八个大洲进行修行，第八个大洲由 $n$ 个城市和 $m$ 条道路构成，道路是双向的。到达第 $i$ 个城市时，qo 可以掌握该城市能学到的全部内容，并获得 $a_i$ 点能力提升，但因为在一个城市可以学会的内容有限，多次到达同一个城市不会多次提升能力。

第八个大洲对能力也有很严的要求，对于第 $i$ 条道路，只有能力大于等于 $b_i$ 的人才能经过。

qo 准备乘坐火箭去往第八个大洲，飞机可以降落在任意城市（即可以在任意城市开始进修），qo 想知道自己的能力最多可以成长为多少，所以 qo 提出了 $Q$ 次询问，第 $i$ 次询问为：当自己初始能力为 $q_i$ 时，能力最多可以成长为多少。

【输入格式】

第一行三个整数 $n, m, Q$。

接下来一行 $n$ 个非负整数，分别代表 $a_1$ 到 $a_n$。

接下来 $m$ 行，每行三个正整数，$u_i, v_i, b_i$，表示城市 $u_i$ 和城市 $v_i$ 之间有一条道路，限制为 $b_i$。

最后 $Q$ 行，每行一个非负整数 $q_i$。

【输出格式】

$Q$ 行，每行一个整数表示答案。

【样例输入1】

2 1 1
10 10
1 2 10
0

【样例输出1】

20

【样例输入2】

4 4 2
2 3 4 5
1 2 7
2 3 5
3 4 8
4 1 10
0
1

【样例输出2】

5
15

【数据范围】

对于前 $20\%$ 的数据 $n\le 5,m\le 10,Q=1$。

对于前 $30\%$ 的数据 $n\le50,m\le100,Q\le5$。

对于前 $40\%$ 的数据 $n\le100,m\le200,Q\le5$。

对于前 $50\%$ 的数据 $n\le300,m\le600,Q\le100$。

对于前 $60\%$ 的数据 $n\le1000,m\le2000,Q\le1000$。

对于另外 $10\%$ 的数据 $n\le 1000,m=n-1,Q\le1000$，图保证连通。

对于另外 $10\%$ 的数据 $m=n-1$，图保证连通。

对于 $100\%$ 的数据 $1\le n,Q\le 10^5$，$0\le m\le 2\times10^5$，$0\le a_i\le 10^4$，$0\le q_i,b_i\le10^9$。