题目背景

huhe 是一位资深的游戏玩家，最近迷上了一款冒险类 RPG 游戏。在游戏世界中，huhe 被困在了初始城镇（编号 1），而他的目标是到达最终的宝藏城镇（编号 n）获取稀有奖励。

题目描述

游戏世界中有 $n$ 个城镇，编号为 $1,2,3,\ldots,n$。 城镇之间有 $m$ 条双向的道路，连接着两个城镇。每次通过某条道路从一个城镇到另一个城镇，huhe 操控的角色会消耗一定的体力值（体力值可理解为游戏中的血条）。 每次进入一个城镇（包括初始城镇和宝藏城镇），都需要消耗该城镇对应的「入场券点数」（点数为非负整数）。道路本身不会额外消耗点数。

huhe 的角色初始体力值为 $b$（体力值上限也为 $b$），体力值一旦降至负数，角色就会死亡，无法到达宝藏城镇。 huhe 希望尽可能节省「入场券点数」的消耗，他想知道：在所有能成功到达宝藏城镇的路线中，路线上经过的所有城镇的「入场券点数」的最大值，最小可以是多少？

输入格式

第一行包含 3 个正整数 $n, m, b$，分别表示城镇数量、道路数量、角色初始体力值。

接下来 $n$ 行，每行 1 个非负整数 $f_i$，表示进入第 $i$ 个城镇需要消耗的入场券点数。

再接下来 $m$ 行，每行 3 个正整数 $a_i, b_i, c_i$（$1\leq a_i,b_i\leq n$），表示城镇 $a_i$ 和 $b_i$ 之间有一条双向道路，通过该道路会消耗 $c_i$ 点体力值。

输出格式

仅一个整数，表示满足条件的「入场券点数最大值」的最小值。 如果无法到达宝藏城镇，输出 AFK。

输入输出样例 #1

输入 #1

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

输出 #1

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$，可能有两条边连接着相同的城市。