图论！

这题有负环，所以要用dijkstra（个人叫它迪结哥斯拉）

先是可爱的链式前向星（存图，比派蒙还可爱）

int vtx[N],head[N],ntx[N],w[N],idx;
void add(int a,int b,int c){
	ntx[idx]=head[a];
	head[a]=idx;
	vtx[idx]=b;
	w[idx]=c;
	idx++;
} 

然后就是可爱的核心代码（和纳西妲一样可爱）

void dijkstra(int x){
	memset(visited,0,sizeof(visited));
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	q.push({dis[1],1});
	while(q.size()){
		Node tt=q.top();
		q.pop();
		int k=tt.v;
		if(visited[k]){
			continue;
		}
		visited[k]=true;
		for(int i=head[k];i!=-1;i=ntx[i]){
			int j=vtx[i];
			if(cnt[j]>x){
				continue;
			}
			if(dis[j]>dis[k]+w[i]){
				dis[j]=dis[k]+w[i];
				q.push({dis[j],j});
			}
		}
	}
}

然后附上超级可爱全代码（离可莉的可爱程度只差一点，不要直接抄，再看看有哪里错了）

#include<bits/stdc++.h>
using namespace std;
const int N=10e6+5;
int dis[N];
int vtx[N],head[N],ntx[N],w[N],idx;
bool visited[N];
struct Node{
	int dis;
	int v;
	bool operator <(const Node &b) const{
		return  dis>b.dis;
	}
};
void add(int a,int b,int c){
	ntx[idx]=head[a];
	head[a]=idx;
	vtx[idx]=b;
	w[idx]=c;
	idx++;
} 
int n,m,b,cnt[N];
priority_queue<Node> q;
void dijkstra(int x){
	memset(visited,0,sizeof(visited));
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	q.push({dis[1],1});
	while(q.size()){
		Node tt=q.top();
		q.pop();
		int k=tt.v;
		if(visited[k]){
			continue;
		}
		visited[k]=true;
		for(int i=head[k];i!=-1;i=ntx[i]){
			int j=vtx[i];
			if(cnt[j]>x){
				continue;
			}
			if(dis[j]>dis[k]+w[i]){
				dis[j]=dis[k]+w[i];
				q.push({dis[j],j});
			}
		}
	}
}
int main(){
	cin>>n>>m>>b;
	memset(head,-1,sizeof(head));
	int l=1e9,r=0;
	for(int i=1;i<=n;i++){
		cin>>cnt[i];
		r=max(cnt[i],r);
	}
	l=max(cnt[1],cnt[n]);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	while(l<r){
		int mid=(l+r)/2;
		dijkstra(mid);
		if(dis[n]>b){
			l=1+mid;
		}else{
			r=mid;
		}
	}
	dijkstra(l);
	if(dis[n]>b){
		cout<<"你干嘛哈嗨哟"<<endl;
	}else{
		cout<<n<<endl;
	}
	return 0;
}