该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小 A 在开车的时候被传送到异世界了。

题目描述

在这个异世界，有 $n$ 个土著部落。编号为 $1,2\dots n$。

这个异世界有 $m$ 条双向的土路，第 $i$ 条土路连接部落 $x_i$ 和部落 $y_i$，开车经过这条土路需要耗费 $w_i$ 升汽油。

每经过一个部落，小 A 就要和部落首领周旋，小 A 的口才值至少为 $f_i$ 才能安全离开第 $i$ 个部落 。

假设 $1$ 为出发点，$n$ 为离开异世界的传送门，不巧的是，汽车的油箱只剩下 $b$ 升汽油，并且这个异世界显然没有加油站，如果他在汽油用完前还没到达传送门（在用完的那一刻到达传送门是可以的），那么他只好留在异世界当土著了。

小 A 从一个商人那里搞到了一张地图，记录了整个大陆的信息，他想知道，在所有能在汽油耗尽前的路径中，对口才值的最低要求是多少。

输入格式

第一行 $3$ 个正整数，$n,m,b$。分别表示有 $n$ 个部落，$m$ 条土路，汽车油箱还剩下 $b$ 升汽油。

接下来 $n$ 行，每行 $1$ 个正整数$f_i$，表示安全离开第 $i$ 个部落所需要的口才值 $f_i$。

再接下来 $m$ 行，每行 $3$ 个正整数，$x_i,y_i,c_i$（$1\leq a_i,b_i\leq n$）。表示城市 $x_i$ 和部落 $y_i$ 之间有一条土路，经过这条土路需要 $w_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$，可能有两条不同的土路连接相同的两个部落。