迪杰斯特拉，但是check和dij是分开来写的，看dalao们都是放一起的qwq

#include <bits/stdc++.h>
#define int long long
#define rg register
using namespace std;
int n,m,b,f[10005],dis[10005],obs[10005],ans,l,r;
bool vis[10005];
struct aa{
	int b,v;
};
vector<aa> v[10005]; 
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
inline void dijkstra(){
	q.push({0,1});
	vis[1]=1;
	dis[1]=0;
	while(!q.empty()){
		int a=q.top().first,b=q.top().second;//a距离 b点
		q.pop();
		for(rg int i = 0; i < v[b].size(); i++ ){
			int bb=v[b][i].b,vv=v[b][i].v;
			if(vis[bb]) continue;
			vis[bb]=1;
			if(dis[bb]>dis[b]+vv){
				dis[bb]=dis[b]+vv;
				q.push({dis[bb],bb});
			} 
		} 
	}
}
queue<int> qq;
inline bool check(int x){
	if(x<f[1]) return false;
	int _max=f[1];
	qq.push(1);
	vis[1]=1;
	while(!qq.empty()){
		int now=qq.front();
		qq.pop();
		for(rg int i = 0; i < v[now].size(); i++ ){
			int b=v[now][i].b,a=v[now][i].v;
			if(!vis[b]&&!obs[b]){
				vis[b]=1;
				qq.push(b);
				_max=max(_max,f[b]);
			}
		}
	}
	return _max<=x;
}
signed main(){
	memset(dis,63,sizeof(dis));
	scanf("%lld%lld%lld",&n,&m,&b);
	for(rg int i = 1; i <= n; i++ ){
		scanf("%lld",f+i);
		
		r=max(r,f[i]);
	}
	l=max(f[1],f[n]);
	for(rg int i = 0; i < m; i++ ){
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	dijkstra();
	if(dis[n]>b){
		printf("AFK");
		return 0;
	}
	for(rg int i = 1; i <= n; i++ ){
		if(dis[i]>b) obs[i]=1;
	}
	while(l<=r){
		int mid=(l+r)>>1;
		memset(vis,0,sizeof(vis));
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	printf("%lld",ans);
	return 0;
}