include<bits/stdc++.h>

using namespace std; struct uu { long long s,i; }; bool operator<(uu a,uu b) { return a.s<b.s; } bool b[10005]; long long n,m,bb,a[10005],mm,mn=LONG_LONG_MAX,d[10005]; vector<uu>v[10005]; bool check(long long o) { memset(b,0,sizeof(b)); for(int i=1;i<=n;i++) { d[i]=1000000000000; if(a[i]>o) { b[i]=true; } } priority_queue<uu>q; uu p; p.i=1; p.s=0; q.push(p); d[1]=0; while(1) { while(!q.empty()&&b[q.top().i]) { q.pop(); } if(q.empty()) { return false; } long long x=q.top().i; b[x]=true; q.pop(); if(x==n) { return d[n]<=bb; } for(int j=0;j<v[x].size();j++) { if(b[v[x][j].i]) { continue; } d[v[x][j].i]=min(d[v[x][j].i],d[x]+v[x][j].s); uu p; p.i=v[x][j].i; p.s=v[x][j].s; q.push(p); } } return false; } void read(int &s) { char c=getchar(); while(!isdigit(c)) { c=getchar(); } while(isdigit(c)) { s=(s<<3)+(s<<1)+(c-48); c=getchar(); } } int main() { cin>>n>>m>>bb; for(int i=1;i<=n;i++) { cin>>a[i]; mm=max(mm,a[i]); mn=min(mn,a[i]); } for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; uu w; w.i=y; w.s=z; v[x].push_back(w); w.i=x; v[y].push_back(w); } long long l=max(a[1],max(a[n],mn)),r=mm; while(l<r) { long long h=(l+r)/2; if(check(h)) { r=h; } else { l=h+1; } } if(!check(l)) { cout<<"AFK"<<endl; return 0; } cout<<l<<endl; }