Subtask #1最后一个点过不了，蒟蒻求助！！！

#include <bits/stdc++.h>
#define int long long
#define INF 100000000000000
using namespace std;
int n,m,b,lc[10005],lala[10005];
int vis[10005],l=1;

struct edge{int to, w;};
vector <edge> e[10005];
struct po{int a, b;};
bool operator < (po x, po y) {return x.b > y.b;}
priority_queue <po> q;
void add(int x, int y, int z){e[x].push_back((edge){y, z});}

int dij(int ans) 
{
    for(int i=1;i<=n;i++)lc[i]=INF;
    memset(vis,0,sizeof(vis));
    q.push((po){1, 0}); lc[1] = 0;
    while(!q.empty()) 
    {
        po now = q.top(); q.pop();
        int u = now.a;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = 0; i < e[u].size(); i++) 
        {
//          cout<<"*";
            edge E = e[u][i];
            if(lc[E.to]>lc[u]+E.w&&lala[E.to]<=ans) 
            {
                lc[E.to] = lc[u] + E.w;
                q.push((po){E.to, lc[E.to]});
            }
        }
    }
//    cout<<lc[n]<<endl;
    if(lc[n]>b)return 0;
    else return 1;
}

signed main() 
{
//  freopen("lala.in","r",stdin);
//  freopen("lala.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&b);
    for(int i=1;i<=n;i++)scanf("%lld",&lala[i]);
    for(int i = 1, u, v, w; i <= m; i++) 
    {
        scanf("%lld%lld%lld", &u, &v, &w);
        if(u==v)continue;
        add(u,v,w);add(v,u,w);
    }
    if(!dij(0x7fffffff))
    {
        cout<<"AFK";
        return 0;
    }

    for(int i=(1<<30);i>=1;i>>=1)
        if(!dij(i+l)&&i+l<=0x7fffffff)l+=i;

    cout<<l+1;

}