求条

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll n,m,b,x,y,l,dis[N],f[N],ff[N],pre[N],q[5*N],cnt;
struct node{
    ll f,t,l,n;
}a[10*N];
void add(ll x,ll y,ll l){
    a[++cnt].f=x;
    a[cnt].t=y;
    a[cnt].l=l;
    a[cnt].n=pre[x];
    pre[x]=cnt;
}
bool check(ll mid){
    if(f[1]>mid || f[n]>mid){
        return 0;
    }
    ll head=1,tail=1;
    q[1]=1;
    ff[1]=1;
    dis[1]=0;
    while(head<=tail){
        ll from=q[head];
        for(ll i=pre[from];i;i=a[i].n){
            ll to=a[i].t;
            ll len=a[i].l;
            if(f[to]<=mid){
                if(dis[from]+len<dis[to]){
                    dis[to]=dis[from]+len;
                    if(f[to]==0){
                        f[to]=1;
                        q[++tail]=to;
                    }
                }
            }

        }
        f[from]=0;
        head++;
    }
    if(dis[n]<=b) return 1;
    else return 0;
}
int main(){
    cin>>n>>m>>b;
    for(int i=1;i<=m;i++){
        cin>>f[i];
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y>>l;
        add(x,y,l);
        add(y,x,l);
    }
    ll l=1,r=1e9;
    while(l<=r){
        ll mid=l+(r-l)/2;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    if(l>1e9) cout<<"AFK";
    else cout<<l;
}