题目描述

边境线上有 $n$ 座城市，城市编号为 $1 \sim n$。

第 $i$ 座城市设有一处安检站，想要经过这座城市，就必须接受安检并支付费用 $a_i$。一条旅行路线经过了哪些城市，就需要考虑这些城市中的最大安检费用。

城市之间有 $m$ 条双向道路。第 $j$ 条道路连接城市 $u_j, v_j$，通过这条道路需要消耗体力 $w_j$。

现在，Aki 想从城市 $1$ 出发前往城市 $n$。他一共只能承受不超过 $B$ 的道路体力消耗，也就是整条路线满足：

在所有满足体力限制的路线中，你需要帮他让“路线中出现的最大安检费用”尽量小。

如果无论如何都无法在体力限制内到达城市 $n$，输出 AFK。

输入格式

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

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每座城市的安检费用。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示城市 $u$ 和城市 $v$ 之间有一条双向道路，单次通过这条道路需要消耗体力 $w$。

数据范围：

• $1 \le n \le 5 \times 10^4$
• $1 \le m \le 10^5$
• $1 \le a_i \le 10^9$
• $1 \le w \le 10^6$
• $1 \le B \le 10^{12}$

输出格式

输出一行：

• 若存在可行路线，输出最小可能的“路线最大安检费用”；
• 否则输出 AFK。

5 6 7
5 1 7 3 4
1 2 2
2 5 2
1 3 1
3 4 1
4 5 1
2 4 3

5