题目描述

有 $n$ 座城市和 $m$ 条双向道路。经过城市 $i$ 时需要支付费用 $f_i$，通过一条道路会损失一定血量。

旅人从 $1$ 号城市出发，要到达 $n$ 号城市，初始血量为 $b$。如果总损失血量超过 $b$，就不能成功到达。

在所有可行路线中，关注这条路线经过城市的最大单次费用。请让这个最大费用尽可能小，并输出最小值。

输入格式

第一行输入 $n,m,b$。

接下来 $n$ 行，每行输入一个整数 $f_i$，表示经过城市 $i$ 的费用。

接下来 $m$ 行，每行输入 $a_i,b_i,c_i$，表示城市 $a_i$ 与城市 $b_i$ 之间有一条双向道路，通过会损失 $c_i$ 点血量。

输出格式

如果能到达 $n$ 号城市，输出路线中最大单次城市费用的最小可能值。

如果无法到达，输出 AFK。

样例

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

10

样例说明

数据范围

• 对于 $60\%$ 的数据，$n\le 200$，$m\le 10^4$，$b\le 200$。
• 对于 $100\%$ 的数据，$1\le n\le 10^4$，$1\le m\le 5\times 10^4$，$1\le b\le 10^9$，$1\le c_i\le 10^9$，$0\le f_i\le 10^9$。可能存在多条道路连接同一对城市。