//https://www.luogu.com.cn/problem/P1462?contestId=96625
#include<bits/stdc++.h>
using namespace std;

struct Node
{
? ?long long v;//臨接點(diǎn)
? ?long long w;//邊權(quán)
? ?friend bool operator < (const Node &n1 , const Node &n2)
? ?{
? ? ? ?return n1.w > n2.w;
? ?}
};
//bool operator < (Node lhs , Node rhs)
//{
// ? ?return lhs.w > rhs.w;
//}

#define maxn 10010

long long n,m;
long long b;
long long f[maxn];//點(diǎn)權(quán)值
vector<Node> G[maxn];

long long dist[maxn];
bool visited[maxn];
priority_queue <Node> h;
bool dijsktra(long long x)//此時(shí)的限制點(diǎn)權(quán)為x
{
? ?if(f[1]>x||f[n]>x) return false;//起點(diǎn)終點(diǎn)超過最大點(diǎn)權(quán)
? ?fill(dist,dist+maxn,LONG_LONG_MAX);
? ?fill(visited,visited+maxn,false);
? ?//核心：如果此時(shí)的點(diǎn)權(quán)超過最大值則完全設(shè)置為訪問
? ?for(int i=1;i<=n;i++)
? ?{
? ? ? ?if(f[i]>x)
? ? ? ? ? ?visited[i] = true;
? ?}
? ?dist[1]=0;
? ?h.push(Node{1,0});
? ?while(h.empty()==false)
? ?{
? ? ? ?long long midnode = h.top().v;
? ? ? ?h.pop();
? ? ? ?if(visited[midnode]==true)
? ? ? ? ? ?continue;
? ? ? ?visited[midnode]=true;
? ? ? ?for(int j=0;j<G[midnode].size();j++)
? ? ? ?{
? ? ? ? ? ?long long v=G[midnode][j].v;
? ? ? ? ? ?long long weight=G[midnode][j].w;
? ? ? ? ? ? ? ?if (dist[v] > dist[midnode] + weight)
? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ?dist[v] = dist[midnode] + weight;
? ? ? ? ? ? ? ? ? ?h.push(Node{v, dist[v]});
? ? ? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?if(dist[n]<b)
? ? ? ?return true;
? ?else
? ? ? ?return false;
}

int main()
{
? ?long long maxx = -1 ;//maxx記錄的是最大費(fèi)用
? ?scanf("%lld%lld%lld",&n,&m,&b);
? ?for(int i=1;i<=n;i++)
? ?{
? ? ? ?scanf("%lld",&f[i]);
? ? ? ?if(f[i]>maxx)
? ? ? ? ? ?maxx = f[i];
? ?}

? ?//存儲(chǔ)圖
? ?long long t1,t2,tc;
? ?for(int i=1;i<=m;i++)
? ?{
? ? ? ?scanf("%lld%lld%lld",&t1,&t2,&tc);
? ? ? ?if(t1 == t2) continue;//題中說明：可能有兩條邊連接著相同的城市。
? ? ? ?G[t1].push_back(Node{t2,tc});
? ? ? ?G[t2].push_back(Node{t1,tc});
? ?}

? ?//二分點(diǎn)權(quán)
? ?long long l = 1;//最小點(diǎn)權(quán)
? ?long long r =maxx;//最大點(diǎn)權(quán)
? ?long long mid;
? ?long long ans = -1;
? ?while(l<=r)
? ?{
? ? ? ?mid = (l+r)/2;//限制最大點(diǎn)權(quán)
? ? ? ?if(dijsktra(mid))
? ? ? ?{
? ? ? ? ? ?//如果此次限制可以走通繼續(xù)二分
? ? ? ? ? ?ans = mid ;
? ? ? ? ? ?r ? = mid -1;
? ? ? ?}
? ? ? ?else
? ? ? ?{
? ? ? ? ? ?l = mid + 1;
? ? ? ?}
? ?}

? ?if(ans == -1)
? ?{
? ? ? ?//走不通
? ? ? ?printf("AFK");
? ?}
? ?else
? ?{
? ? ? ?printf("%lld",l);
? ?}
? ?return 0;
}