You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。

有一天他醒来后发现自己居然到了联盟的主城暴风城。

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。

题目描述

在艾泽拉斯，有 $n$ 个城市。编号为 $1,2,3,\ldots,n$。

城市之间有 $m$ 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设 $1$ 为暴风城，$n$ 为奥格瑞玛，而他的血量最多为 $b$，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

歪嘴哦不希望花很多钱，他想知道，在所有可以到达奥格瑞玛的道路中，对于每条道路所经过的城市收费的最大值，最小值为多少。

输入格式

第一行 $3$ 个正整数，$n,m,b$。分别表示有 $n$ 个城市，$m$ 条公路，歪嘴哦的血量为 $b$。

接下来有 $n$ 行，每行 $1$ 个正整数，$f_i$。表示经过城市 $i$，需要交费 $f_i$ 元。

再接下来有 $m$ 行，每行 $3$ 个正整数，$a_i,b_i,c_i$（$1\leq a_i,b_i\leq n$）。表示城市 $a_i$ 和城市 $b_i$ 之间有一条公路，如果从城市 $a_i$ 到城市 $b_i$，或者从城市 $b_i$ 到城市 $a_i$，会损失 $c_i$ 的血量。

输出格式

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出 AFK。

4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

10

提示

对于 $60\%$ 的数据，满足 $n\leq 200$，$m\leq 10^4$，$b\leq 200$；

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^4$，$1\leq m\leq 5\times 10^4$，$1\leq b\leq 10^9$；

对于 $100\%$ 的数据，满足 $1\leq c_i\leq 10^9$，$0\leq f_i\leq 10^9$，可能有两条边连接着相同的城市。