玄1关

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const long long N=1e6+10;
const long long M=1e3+10;

long long n,m,b;
long long f[N];
long long maxuse=-0x7fffffff;
struct Node{
	long long next;
	long long to;
	long long w;//损失血量 
}e[N];
long long head[N];
void init(){
	cin>>n>>m>>b;
	for(long long i=1;i<=n;i++){
		cin>>f[i];
		maxuse=max(maxuse,f[i]);
	}
	long long cnt=0;
	for(long long i=1;i<=m;i++){
		long long u,v,w;
		cin>>u>>v>>w;
		e[++cnt].next=head[u];
		head[u]=cnt;
		e[cnt].to=v;
		e[cnt].w=w;
		e[++cnt].next=head[v];
		head[v]=cnt;
		e[cnt].to=u;
		e[cnt].w=w;
	}
}
queue<long long> que;
long long pd[N];
long long dis1[N];
long long dis2[N];
map<int,int> to1;
map<int,int> to2;
//long long to1[N];
//long long to2[N];
void spfa1(long long start){
	long long k=start;
	for(long long i=1;i<=n;i++){
		dis1[i]=0x7fffffff;
		//pd[i]=false;
	}
	dis1[k]=0;
	pd[k]=true;
	que.push(k);
	while(!que.empty()){
		k=que.front();
		que.pop();
		pd[k]=false;
		for(long long i=head[k];i;i=e[i].next){
			if(dis1[e[i].to]>dis1[k]+e[i].w){
				dis1[e[i].to]=dis1[k]+e[i].w;
				to1[e[i].to]=k;
				if(!pd[e[i].to]){
					que.push(e[i].to);
					pd[e[i].to]=true;
				}
			}
		}
	}
}
void spfa2(long long start){
	long long k=start;
	for(long long i=1;i<=n;i++){
		dis2[i]=0x7fffffff;
		pd[i]=false;
	}
	dis2[k]=0;
	pd[k]=true;
	que.push(k);
	while(!que.empty()){
		k=que.front();
		que.pop();
		pd[k]=false;
		for(long long i=head[k];i;i=e[i].next){
			if(dis2[e[i].to]>dis2[k]+e[i].w){
				dis2[e[i].to]=dis2[k]+e[i].w;
				to2[e[i].to]=k;
				if(!pd[e[i].to]){
					que.push(e[i].to);
					pd[e[i].to]=true;
				}
			}
		}
	}
}
long long find_road_max(long long begin,long long end,long long li){
	long long maxx=-0x7fffffff;
	long long k;
	if(li==1){
		maxx=max(maxx,f[begin]);
		k=end;
		while(k!=0){
			maxx=max(maxx,f[k]);
			k=to1[k];
		}
	}
	if(li==2){
		maxx=max(maxx,f[begin]);
		k=end;
		while(k!=0){
			maxx=max(maxx,f[k]);
			k=to2[k];
		}
	}
	return maxx;
}
bool check(long long k){
	for(long long i=1;i<=n;i++){
		if(find_road_max(1,i,1)<=k&&find_road_max(i,n,2)<=k){
			return true;
		}
	}
	return false;
}
int main(){
	init();
	spfa1(1);
	spfa2(n);
	if(dis1[n]>b){
		cout<<"AFK";
		return 0;
	}
	long long l=0,r=maxuse;
	long long mid;//二分最小花费 
	while(l<=r){
		mid=(l+r)/2;
		if(check(mid)){
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<mid;
	return 0;
}