rt,WA#7#8#11

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+100,M=5e4+100,inf=1e18;
struct edge{int nxt,to,dis;}e[M<<1];
struct node{int x,dis;bool operator<(const node&x)const{return x.dis<dis;}};
int n,m,b,s,u,v,w,l,r,ans,cnt,f[N],head[N],vis[N],dis[N];priority_queue<node>q;
void add(int a,int b,int c){++cnt,e[cnt].dis=c,e[cnt].to=b,e[cnt].nxt=head[a],head[a]=cnt;}
int dij(int mx){
	memset(vis,0,sizeof vis);for(int i=1;i<=n;i++)dis[i]=inf;dis[s]=0;
	q.push({s,0});
	while(!q.empty()){
		node fr=q.top();q.pop();
		if(vis[fr.x])continue;
		vis[fr.x]=1;
		for(int i=head[fr.x];i;i=e[i].nxt){
			int t=e[i].to;
			if(f[t]<=mx&&dis[t]>dis[fr.x]+e[i].dis){
				dis[t]=dis[fr.x]+e[i].dis;
				if(!vis[t])q.push({t,dis[t]});
			}
		}
	}return dis[n]<=mx;
}signed main(){
	cin>>n>>m>>b,s=1;
	for(int i=1;i<=n;i++)cin>>f[i],r=max(r,f[i]);l=max(f[1],f[n]);
	for(int i=1;i<=m;i++)cin>>u>>v>>w,add(u,v,w),add(v,u,w);
	while(l<=r){
		int mid=l+r>>1;
		if(dij(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}return ans?cout<<ans:cout<<"AFK",0;
}