#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}
int n,m,b;
int price[10001];
vector<pair<int,int> > g[50001];
int vis[10001];
void dfs(int mi,int now,int nowbl)
{
	for(int i=0;i<g[now].size();i++)
	{
		//cout<<now<<" "<<vis[g[now][i].first]<<" "<<price[vis[g[now][i].first]]<<" "<<nowbl-g[now][i].second<<endl;
		if(!vis[g[now][i].first]&&price[g[now][i].first]<=mi&&nowbl-g[now][i].second>=0)
		{
			//cout<<now<<" "<<g[now][i].first<<endl;
			vis[g[now][i].first]=true;
			dfs(mi,g[now][i].first,nowbl-g[now][i].second);
		}
	}
}
bool check(int mi)
{
	if(price[1]>mi)
	{
		return false;
	}
	for(int i=1;i<=n;i++)
	{
		vis[i]=false;
	}	
	vis[1]=true;
	dfs(mi,1,b);	
	return vis[n];
}
signed main()
{
	cin>>n>>m>>b;
	for(int i=1;i<=n;i++)
	{
		cin>>price[i];
	}
	for(int i=1;i<=m;i++)
	{
		int from,to,blood;
		cin>>from>>to>>blood;
		g[from].push_back(make_pair(to,blood));
		g[to].push_back(make_pair(from,blood));
	}
	//cout<<check(0);
	//system("pause");
	int l=0,r=INT_MAX,mid,ans=-1;
	while(l<=r)
	{
		mid=l+r>>1;
		//cout<<l<<" "<<r<<" "<<mid<<endl;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1; 
		}
	}
	if(ans==-1)
	{
		cout<<"AFK";
	}
	else
	{
		cout<<ans;
	}
}

64分求助