Rt__ @ 2024-09-24 11:30:25
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N=5000010;
int n,m;
ll cw[N],b;
int h[N],idx,e[N],ne[N];
ll w[N];
ll d[N];
void add(int a,int b,ll c){
ne[idx]=h[a],e[idx]=b,w[idx]=c,h[a]=idx++;
return ;
}
struct node{
int i;
ll w;
bool operator<(const node a)const{
return w>a.w;
}
}maxc[N];
bool cmp(node a,node b){
return a.w<b.w;
}
bool dij(int x){
if(cw[1]>cw[x])return false;
priority_queue<node>q;
memset(d,0x3f,sizeof d);
d[1]=0;
q.push({1,0});
while(q.size()){
node now=q.top();
q.pop();
int u=now.i,dist=now.w;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(cw[j]>cw[x])continue;
if(d[j]>dist+w[i]){
d[j]=dist+w[i];
q.push({j,d[j]});
}
}
}
ll ans=d[x];
if(ans>b)return false;
memset(d,0x3f,sizeof d);
q.push({x,0});
d[x]=0;
while(q.size()){
node now=q.top();
q.pop();
int u=now.i,dist=now.w;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(cw[j]>cw[x])continue;
if(d[j]>dist+w[i]){
d[j]=dist+w[i];
q.push({j,d[j]});
}
}
}
if(ans+d[n]>b)return false;
return true;
}
signed main(){
memset(h,-1,sizeof h);
cin>>n>>m>>b;
for(int i=1;i<=n;i++){
cin>>cw[i];
maxc[i]={i,cw[i]};
}
sort(maxc+1,maxc+1+n,cmp);
for(int i=1;i<=m;i++){
int a,b;
ll c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
/* int yy=10;
while(yy--){
int xx;
cin>>xx;
cout<<dij(xx);
cout<<endl;
}*/
for(int i=n;i>=1;i--){
if(!dij(maxc[i].i)){
cout<<"AFK";
return 0;
}
if(maxc[i].w!=maxc[i-1].w)break;
}
int l=0,r=n;
while(l<r){
int mid=(l+r)>>1;
bool c=dij(maxc[mid].i);
if(c){
r=mid;
}
else{
l=mid+1;
}
}
cout<<maxc[l].w;
return 0;
}
救救孩子吧