### 题目背景  

在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量。

有一天他醒来后，发现自己居然到了联盟的主城暴风城。  

在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛。  

### 题目描述

在艾泽拉斯，有 $n$ 个城市，编号为 $1,2,3,\cdots,n$。

城市之间有 $m$ 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点），路上并没有收费站。

假设 $1$ 为暴风城，$n$ 为奥格瑞玛，而他的血量最多为 $b$，出发时他的血量是满的。

歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

### 输入格式  

第一行三个正整数 $n,m,b$，分别表示有 $n$ 个城市，$b$ 条公路，歪嘴哦的血量为 $b$。

接下来有 $n$ 行，每行一个正整数 $f_i$，表示经过城市 $i$，需要交费 $f_i$ 元。

再接下来有 $m$ 行，每行三个正整数 $a_i,b_i,c_i$。表示城市 $a_i$ 和城市 $b_i$ 之间有一条双向公路，如果从城市 $a_i$ 到城市 $b_i$，或者从城市 $b_i$ 到城市 $a_i$，会损失 $c_i$ 的血量。

### 输出格式  

仅一个整数，表示歪嘴哦交费最多的一次的最小值。

如果他无法到达奥格瑞玛，输出 ```AFK```。  

### 说明/提示

对于 $60\%$ 的数据，满足 $n\le200,m\le10^4,b\le200$；

对于 $100\%$ 的数据，满足 $1\le n\le10^4,1\le m\le5\times 10^4,1\le b,f_i,c_i\le10^9,1\le a_i,b_i\le n$。

**不保证不存在重边或自环。**