#include<bits/stdc++.h>
using namespace std;
long long n,m,b,bb,a,w,s,e,maxf,ans=-1;
struct Bian{
	long long b,q;
};
struct Dian{
	bool l;
	long long f;
	vector<Bian> Bs;
}Ds[11111];
struct Dan{
	long long v,t,xl;
	bool operator < (const Dan &A)const{
		return A.t<t;
	}
};
bool bfs(long long x){
	for(long long i=1;i<=n;i++){
		Ds[i].l=0;
	}
	priority_queue<Dan> que;
	que.push({1,Ds[1].f});
	while(!que.empty()){
		Dan qs=que.top();
		que.pop();
		if(!Ds[qs.v].l&&qs.xl>=0&&qs.t<=x){
			Ds[qs.v].l=1;
		}
		else{
			continue;
		}
		if(qs.v==n){
			return 1;
		}
		for(long long i=0;i<Ds[qs.v].Bs.size();i++){
			if(!Ds[Ds[qs.v].Bs[i].b].l){
				que.push({Ds[qs.v].Bs[i].b,max(qs.t,Ds[Ds[qs.v].Bs[i].b].f),qs.xl-Ds[qs.v].Bs[i].q});
			}
		}
	}
	return 0;
}
int main(){
	cin>>n>>m>>b;
	for(long long i=1;i<=n;i++){
		cin>>Ds[i].f;
		maxf=max(maxf,Ds[i].f);
	}
	for(long long i=0;i<m;i++){
		cin>>a>>bb>>w;
		Ds[a].Bs.push_back({bb,w});
		Ds[bb].Bs.push_back({a,w});
	}
	e=1000000000;
	while(s<e){
		long long mid=(s+e)/2;
		if(bfs(mid)){
			e=mid;
			ans=e;
		}
		else{
			s=mid+1;
		}
	}
	if(ans==-1){
		cout<<"AFK";
		return 0;
	}
	cout<<(s+e)/2;
}