样例过了，空间全爆，求条，玄关

数组我都是压着数据范围开的

#include <bits/stdc++.h>
using namespace std;
int n,m,b,u,v,w,maxn=-1,ans=-1,q=0,p;
int f[10005],c[10005][10005]={0},vis[10005]={0};

void check(int x,int y,int h){
    if(h<0) return;
    if(x==n){
        if(q==1){
            ans=max(ans,y);
            p=1;
        }
        return;
    }
    for(int i=2;i<=n;i++){
        if(c[x][i]!=0&&vis[i]==0&&f[i]<=y){
            vis[i]=1;
            if(f[i]==y) q=1;
            check(i,y,h-c[x][i]);
            vis[i]=0;
            if(f[i]==y) q=0;
        }
    }
}

void bin(int l,int r){
    p=0;
    if(l>r) return;
    int mid=(l+r)/2;
    if(mid>=f[1]&&mid>=f[n]) check(1,mid,b);
    if(p==1) bin(l,mid-1);
    else bin(mid+1,r);
}

int main(){
    vis[1]=1;
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>f[i];
        maxn=max(maxn,f[i]);
    }
    if(n==1){
        cout<<f[1];
        return 0;
    }
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        c[u][v]=w;
        c[v][u]=w;
    }
    bin(1,maxn);
    if(ans==-1) cout<<"AFK";
    else cout<<ans;
    return 0;
}