题目背景

在天津有一位名叫小喷菇的老师，他是吃早点的狂热爱好者。

每一天小喷菇都要从家出发，到他喜欢的早点铺吃早点。

题目描述

在天津总共有 $n$ 个路口，编号为 $1,2,3,\dots,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≤a_i,b_i≤n$）。表示路口 $a_i$ 和路口 $b_i$ 之间有一条道路，如果从路口 $a_i$ 到路口 $b_i$，或者从路口 $b_i$ 到路口 $a_i$，会损失 $c_i$ 的体力。

输出格式

仅一个整数，表示小喷菇经过路口整洁值最大值的最小值。

如果他无法到达早点铺，输出 AFK。

输入输出样例

输入 #1

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

输出 #1

10

说明/提示

样例解释：因为必须要经过第 4 个路口（终点），所以结果为 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$，可能有两条边连接着相同的早点铺。