求助，int80分，long long60分

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,b,f[10005],dis[10005];
bool vis[10005];
vector<pair<int,int> > v[10005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
bool dij(int s){
	while(!q.empty()){
		q.pop();
	}
	for(int i=1;i<=n;i++){
		dis[i]=INT_MAX/2;
	}
	memset(vis,0,sizeof(vis));
	q.push({0,1});
	dis[1]=0;
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(!vis[x]){
			vis[x]=1;
			for(int i=0;i<v[x].size();i++){
				int y=v[x][i].first;
				int w=v[x][i].second;
				if(f[y]<=s&&dis[y]>dis[x]+w){
					dis[y]=dis[x]+w;
					if(!vis[y]){
						q.push({dis[y],y});
					}
				}
			}
		}
	}
	return dis[n]!=INT_MAX/2;
}
signed main(){
	cin>>n>>m>>b;
	for(int i=1;i<=n;i++){
		cin>>f[i];
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	if(!dij(1e9+1)){
		cout<<"AFK";
		return 0;
	}
	int l=f[1]-1,r=1e9+1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(dij(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<r;
	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,b,f[10005],dis[10005];
bool vis[10005];
vector<pair<int,int> > v[10005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
inline bool dij(int s){
	while(!q.empty()){
		q.pop();
	}
	for(int i=1;i<=n;i++){
		dis[i]=1e14;
	}
	memset(vis,0,sizeof(vis));
	q.push({0,1});
	dis[1]=0;
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(!vis[x]){
			vis[x]=1;
			for(int i=0;i<v[x].size();i++){
				int y=v[x][i].first;
				int w=v[x][i].second;
				if(f[y]<=s&&dis[y]>dis[x]+w){
					dis[y]=dis[x]+w;
					if(!vis[y]){
						q.push({dis[y],y});
					}
				}
			}
		}
	}
	return dis[n]!=1e14;
}
signed main(){
	cin>>n>>m>>b;
	for(int i=1;i<=n;i++){
		cin>>f[i];
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	if(!dij(1e15)){
		cout<<"AFK";
		return 0;
	}
	int l=f[1]-1ll,r=1e10+1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(dij(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<r;
	return 0;
}