思路：二分+堆优化dijkstra。

判了 AFK，开了 long long，建了双向边，边数开了 $2$ 倍，算上了第一个城市。

谢大佬！

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e4+4,M=1e5+5;
int n,m,HP;
int f[N],maxx;
int h[N],to[M],ne[M],idx,w[M];
int l,r,ans=-114514;
int dist[N];
bool vis[N];
void add(int a,int b,int ww){
	to[++idx]=b;
	w[idx]=ww;
	ne[idx]=h[a];
	h[a]=idx;
}
bool check(int x){
	memset(dist,0x3f,sizeof dist);
	memset(vis,false,sizeof vis);
	dist[1]=0;
	priority_queue<int,vector<int>,greater<int> > heap;
	heap.push(1);
	while(heap.size()){
		int t=heap.top();
		heap.pop();
		if(vis[t]) continue;
		vis[t]=true;
		for(int i=h[t];i!=-1;i=ne[i]){
			int j=to[i];
			if(f[j]<=x&&dist[j]>dist[t]+w[i]){
				dist[j]=dist[t]+w[i];
				heap.push(j);
			}
		}
	}
	return dist[n]<=HP;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof h);
	
	cin>>n>>m>>HP;
	for(int i=1;i<=n;i++) cin>>f[i],maxx=(maxx,f[i]);
	for(int i=1;i<=m;i++){
		int a,b,ww;
		cin>>a>>b>>ww;
		add(a,b,ww);
		add(b,a,ww);
	}
	
	l=max(f[1],f[n]),r=maxx;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	if(ans==-114514) cout<<"AFK"<<endl;
	else cout<<ans<<endl;
	return 0;
}