再DE心脏就受不了了QAQ，WA了#1 #4，Dij堆优化+二分答案

RT，救...命

//也就是说，求最大值的最小值
//mid为花钱上限
//并且看最短路是否超过血量上限了
//也就是个二维的Dij
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
#define maxe 100005
#define inf 2e9
/*存点*/
struct node {
    int id, dis;
    bool operator < (const node& a)const {
        return a.dis < dis;
    }
};
int ndis[maxn];
int fee[maxn];
int used[maxn];
int last[maxn];
int c[maxn];

/*存边*/
int pre[maxe];
int to[maxe];
int val[maxe];

/*其他*/
int tot;
priority_queue<node> qu;

void add(int u, int v, int w) {
    to[++tot] = v;
    val[tot] = w;
    pre[tot] = last[u];
    last[u] = tot;
}
int n, m, b,ans=inf;
int ai, bi, ci;
int main() {
    //起点 0
    //终点 1e9
    scanf("%d%d%d", &n, &m, &b);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &fee[i]);
        c[i] = fee[i];
    }
    sort(c + 1, c + n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &ai, &bi, &ci);
        add(ai, bi, ci);
        add(bi, ai, ci);
    }
    ndis[1] = 0;
    //存图完毕
    int head = 1;
    int tail = n;
    int mid;
    while (head <= tail) {
        mid = (head + tail) / 2;
        //跑一遍dij，滤掉不满足的点
        fill(ndis, ndis + n + 1, inf);
        fill(used, used + n + 1, 0);
        ndis[1] = 0;
        qu.push(node{ 1,0 });
        while (!qu.empty()) {
            int x = qu.top().id;
            int vv = qu.top().dis;
            int ptr = last[x];
            qu.pop();
            if (used[x])continue;
            used[x] = 1;
            while (ptr) {
                int o = to[ptr];
                if (!used[o] && fee[o]<=c[mid] && vv + val[ptr] <= ndis[o]) {
                    ndis[o] = val[ptr] + vv;
                    qu.push(node{ o,ndis[o] });
                }
                ptr = pre[ptr];
            }
        }
        //dij跑完了
        //死了，到不了，右分
        if (ndis[n] > b) { head = mid + 1; }
        //没死，到的了，存值，左分
        else { ans = c[mid]; tail = mid - 1; }
    }
    if (ans == inf) { printf("AFK"); }
    else { printf("%d", ans); }
}