90分，#8tle，吸氧就wa

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const LL N=1e5+10,M=10*N;
const LL INF=1e18;

LL h[N],e[M],ne[M],w[M],idx;//w存边权，就是攻击血量
LL v[N],dist[N];//存点权，就是过路费
bool st[N];
LL n,m,life;

void add(LL a,LL b,LL c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool check(LL mid)
{
    // memset(st,0,sizeof st);
    // memset(dist,0x3f,sizeof dist);

    for(LL i=1;i<=n;i++)
    {
        st[i]=false;
        dist[i]=INF;
    }

    priority_queue<PII,vector<PII>,greater<PII>> heap;
    dist[1]=0,heap.push({0,1});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        LL ver=t.y;

        // cout<<dist[ver]<<endl;
        if(!st[ver]&&v[ver]<=mid)//?
        {
            st[ver]=true;
            for(LL i=h[ver];~i;i=ne[i])
            {
                LL j=e[i];
                if(dist[j]>dist[ver]+w[i]&&v[j]<=mid)
                {

                    heap.push({dist[j],j});
                    dist[j]=dist[ver]+w[i];
                }
            }
        }
    }
    if(dist[n]<=life) return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    FILE *fp;
    // fp=fopen("C:\\Users\\31142\\Desktop","r");

    cin>>n>>m>>life;
    // memset(h,-1,sizeof h)
    for(LL i=1;i<=n;i++) h[i]=-1;
    for(LL i=1;i<=n;i++) cin>>v[i];
    // for(LL i=1;i<=n;i++) fscanf("%d",&v[i]);

    for(LL i=1;i<=m;i++)
    {
        LL a,b,c;
        cin>>a>>b>>c;

        // fscanf(fp,"%ld %ld %ld",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    LL l=v[1],r=1e9+10;
    while(l<r)
    {
        LL mid=l+r>>1;
        // if(v[1]+v[n]>=mid) l=mid+1;
        if(check(mid)) r=mid;
        else l=mid+1;

        // if(!check(mid)) cout<<"qi"<<endl;
    }

    if(r>1e9) cout<<"AFK"<<endl;
    else cout<<r<<endl;

    return 0;
}