萌新求助！！！90分，急

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define REP(i,s,e) for(int i=s;i>=e;i--)
#define LL long long
#define U unsigned
const int N=1e5+5;
int f[N],n,m,b;
LL dis[N];
bool v[N];
queue<int> q;
struct node{
    int x;
    LL l;
};
vector<node> g[N];
bool check(int x){
    if(f[1]>x||f[n]>x)return false;
    memset(dis,0x3f,sizeof(dis));
    memset(v,0,sizeof(v));
    v[1]=1;dis[1]=0;
    q.push(1);
    while(q.size()){
        int u=q.front();q.pop();v[u]=0;
        for(int i=0;i<g[u].size();i++){
            if(f[g[u][i].x]>x)continue;
            if(dis[g[u][i].x]>dis[u]+g[u][i].l){
                dis[g[u][i].x]=dis[u]+g[u][i].l;
                if(!v[g[u][i].x])v[u]=1,q.push(g[u][i].x);
            }
        }
    }
    return dis[n]<=b;
}
int main(){
    scanf("%d%d%d",&n,&m,&b);
    rep(i,1,n)scanf("%d",f+i);
    rep(i,1,m){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back((node){b,c});
        g[b].push_back((node){a,c});
    }
    int l=0,r=1e9,mid,ans;
    bool flag=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1,flag=1;
        else l=mid+1;
    }
    if(flag)cout<<ans<<endl;
    else puts("AFK");
    return 0;
}