#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct Edge {
	long long to,q;
};
struct Pri {
	long long k,q;
};
bool operator < (Pri a,Pri b) {
	return a.q>b.q;
}
long long n,m,b,l,r=-1,p[10005],d[10005];
bool vis[10005],Find,use;
priority_queue <Pri> q;
vector <Edge> v[10005];
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m>>b;
	for(int i=1;i<=n;i++) {
		cin>>p[i];
		r=max(r,p[i]);
	}
	l=max(p[1],p[n]);
	for(int i=1;i<=m;i++) {
		long long x,y,z;
		cin>>x>>y>>z;
		v[x].push_back((Edge){y,z});
		v[y].push_back((Edge){x,y});
	}
	while(l<=r) {
		if(l==r&&use==true) {
			break;
		}
		use=true;
		long long mid=(l+r)/2;
		for(int i=1;i<=n;i++) {
			d[i]=9223372036854775807;
			vis[i]=false;
			if(p[i]>mid) {
				vis[i]=true;
			}
		}
		d[1]=0;
		q.push((Pri){1,0});
		while(!q.empty()) {
			long long k=q.top().k;
			q.pop();
			if(vis[k]==true) {
				continue;
			}
			vis[k]=true;
			for(int i=0;i<v[k].size();i++) {
				if(p[v[k][i].to]>mid) {
					continue;
				}
				if(d[k]+v[k][i].q<d[v[k][i].to]) {
					d[v[k][i].to]=d[k]+v[k][i].q;
					q.push((Pri){v[k][i].to,d[k]+v[k][i].q});
				}
			}
		}
		if(d[n]<b) {
			l=mid;
			Find=true;
		}
		else {
			r=mid-1;
		}
	}
	if(Find) cout<<l<<'\n';
	else cout<<"AFK"<<'\n';
	return 0;
}

不知道为什么有9个TLE和1个WA，自己也找不出错QAQ