rt.
救救我......
验证码gous祭

#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=500010,inf=1145141919;
int to[M],nxt[M],val[M];
int head[N],cnt;
void add(int u,int v,int w){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	val[cnt]=w;
	head[u]=cnt;
}
int n,m,k,l=inf,r,flag;
int num[N],dis[N];
struct node{
	int pos,dis;
	friend bool operator <(node a,node b){
		return a.dis>b.dis;
	}
};
priority_queue<node> q;
bool dijkstra(int x){
	memset(dis,-1,sizeof(dis));
	dis[1]=k;
	q.push({dis[1],1});
	while(!q.empty()){
		int u=q.top().dis,d=q.top().pos;
		q.pop();
		if(dis[u]!=d) continue;
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(num[v]>x) continue;
			if(dis[v]<dis[u]-val[i]&&dis[u]-val[i]>=0){
				dis[v]=dis[u]-val[i];
				q.push({dis[v],v});
			}
		}
	}
	if(dis[n]>=0) return 1;
	return 0;
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i){
		cin>>num[i];
		l=min(l,num[i]);
		r=max(r,num[i]);
	}
	flag=r;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	while(l<=r){
		int mid=(l+r)/2;
		if(dijkstra(mid)) r=mid-1;
		else l=mid+1; 
	}
	if(l>flag) cout<<"AFK";
	else cout<<l;
return 0;}