求$dalao$调代码qwq:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
const int N=50005;
const int inf=INT_MAX;

int n,m,k;
int u,v,w;
int l=inf,r,ans=inf;
int f[N],vis[N];
vector<pii>G[N];
struct node{int x,p,h;};

bool dijsktra(int maxx){
	memset(vis,0,sizeof vis);
	queue<node>q;q.push({1,f[1],k});
	while(!q.empty()){
		node cur=q.front();q.pop();
		if(vis[cur.x])continue;
		vis[cur.x]=1;
		for(int i=0;i<G[cur.x].size();i++){
			int y=G[cur.x][i].first;
			int w=G[cur.x][i].second;
			if(max(cur.p,f[y])<=maxx&&cur.h-w>=0){
				if(y==n)
					return 1;
				q.push({y,max(cur.p,f[y]),cur.h-w});
			}
		}	
	}
	
	return 0;
}

int main(){
	cin>>n>>m>>k;
	
	for(int i=1;i<=n;i++)
		cin>>f[i],
		l=min(l,f[i]),r=max(r,f[i]);
	
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		G[u].push_back(make_pair(v,w));
		G[v].push_back(make_pair(u,w));
	}

	while(l<=r){
		int mid=l+r>>1;
		if(dijsktra(mid))
			r=mid-1,ans=mid;
		else 
			l=mid+1;
	}
	
	if(ans==inf)puts("AFK");
	else cout<<ans<<endl;
	return 0;
}