WA #5 #8 #11 #12

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,b,f[N],dis[N];
bool vis[N];
struct edge{
	int to,w;
	bool operator<(const edge&a)const{return w>a.w;}
};
vector<edge>nbr[N];
int dijkstra(int x){
	fill(dis+1,dis+n+1,1e18);
	fill(vis+1,vis+n+1,0);
	dis[1]=0;
	priority_queue<edge>pq;
	pq.push({1,0});
	for(;!pq.empty();){
		int cur=pq.top().to;
		pq.pop();
		if(vis[cur])continue;
		vis[cur]=1;
		for(auto [to,w]:nbr[cur]){
			if(f[to]>x)continue;
			if(dis[to]>dis[cur]+w){
				dis[to]=dis[cur]+w;
				pq.push({to,dis[to]});
			}			
		}
	}
	return dis[n];
}
signed main(){
	cin>>n>>m>>b;
	int l,r=0;
	for(int i=1;i<=n;i++)cin>>f[i],r=max(r,f[i]);
	l=max(f[1],f[n]);
	for(;m;m--){
		int u,v,w;
		cin>>u>>v>>w;
		nbr[u].push_back({v,w});
		nbr[v].push_back({u,w});
	}
	for(;l+1<r;){
		int mid=l+r>>1;
		if(dijkstra(mid)>b)l=mid;
		else r=mid;
	}
	if(dijkstra(l)>b)cout<<"AFK";
	else cout<<l;
	return 0;
}