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

#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;
}