RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10001+10;
const int maxm=50001+10;
const int INF=0x3f3f3f3f;
int n,m,b,cnt=0,ans=-1;
ll f[maxn],dis[maxn];
int head[maxn];
bool vis[maxn];
struct edge
{
  int next,to,val;
}bian[maxm];
void ins(int u,int v,int c)
{
  bian[++cnt].to=v;
  bian[cnt].val=c;
  bian[cnt].next=head[u];
  head[u]=cnt;
}
bool spfa(int k)
{
  queue <int> q;
  if(f[1]>k)  return false;
  dis[1]=0;vis[1]=true;
  q.push(1);
  while(!q.empty())
  {
    int u=q.front();
    q.pop();
    vis[u]=false;
    for(int e=head[u];e;e=bian[e].next)
      if(dis[bian[e].to]>dis[u]+bian[e].val && f[bian[e].to]<=k)
      {
      	dis[bian[e].to]=dis[u]+bian[e].val;
      	if(!vis[bian[e].to])  {vis[bian[e].to]=true;q.push(bian[e].to);}
	  }
  }
  if(dis[n]>b)  return false;
  return true;
}

int main()
{
	scanf("%d%d%d",&n,&m,&b);
	for(int i=1;i<=n;i++)
	  scanf("%lld",&f[i]);
	for(int i=1;i<=m;i++)
	{
	  int u,v,c;
	  scanf("%d%d%d",&u,&v,&c);
	  ins(u,v,c);
	  ins(v,u,c);
	}
	int l=0,r=1000000001;
	while(l<=r)
	{
	  int mid=(l+r)>>1;
	  memset(vis,false,sizeof(vis));
	  memset(dis,INF,sizeof(dis));
	  if(spfa(mid))  {ans=mid;r=mid-1;}
	  else  l=mid+1;
	}
	if(ans==-1)  printf("AFK");
	else  printf("%d",ans);
	return 0;
}