刚学oi，不知哪错了就20分

#include <cstdio>
#include <queue>
#include <algorithm>
#define res register int
typedef long long ll;
const int mx = 12550;
ll n,m,tot,life,l,r,head[mx],d[mx],p[mx];
bool vis[mx];
std::queue<int> q;
struct edge{
    int to,next,w;
}e[mx<<2];

inline ll max(ll a,ll b){
    return a > b ? a : b; 
} 

inline ll rd(){
    ll x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') { x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*f;
}

inline void write(ll x){
    if(x<0) { putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

inline void add(int x,int y,int z){
    e[++tot].to=y;
    e[tot].w=z;
    e[tot].next=head[x];
    head[x]=tot;
}

inline void init(){
    n=rd(),m=rd(),life=rd();
    for(res i=1;i<=n;i++){
        p[i]=rd();
        r=max(p[i],r);
    }   l=max(p[1],p[n]);
    for(res i=1,x,y,z;i<=m;i++){
        x=rd(),y=rd(),z=rd();
        if(x==y) continue;
        add(x,y,z);
        add(y,x,z);
    }
}

inline bool spfa(int x){
    if(p[1]>x||p[n]>x) return false;
    for(res i=1;i<=n;i++) d[i] = 2147483647;
    d[1]=0;q.push(1);
    while(!q.empty()){
        int u=q.front();vis[u]=0;q.pop();
        for(res i=head[u];i;i=e[i].next){
            int to=e[i].to;
            if(d[to]>d[u]+e[i].w&&p[to]<=x){
                d[to]=d[u]+e[i].w;
                if(!vis[to]){
                    vis[to]=1;
                    q.push(to);
                }
            }
        }
    }
    if(d[n]>life) return false;
    return true;
}

inline void deal(){
    while(l<r){
        int mid = (l+r)>>1;
        if(spfa(mid)) r=mid;
        l=mid+1;
    }
} 

int main(){
//  freopen("std.in","r",stdin);
    init();
    deal();
    if(spfa(l)) write(l);
    else printf("AFK");
    return 0;
}