求条

#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;
}