开O2就RE，不开TLE

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define db double
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Res(i,j,k) for(int i=j;i>=k;i--)
#define Forp(i,j,k) for(int i=j;i<k;i++)

#define endl '\n'
#define mem(a,p) memset(a,p,sizeof a)
#define INF 0x3f3f3f3f
#define LINF LLONG_MAX/3
#define in cin
#define out cout
#define Pt out << '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAXN = 5e4 + 5;

int n,m,b;
struct edge{
	int to,nxt,w;
}e[MAXN];
int tot;
int hd[MAXN];
int f[MAXN];
void add(int u,int v,int w){
	e[++tot].to = v;
	e[tot].w = w;
	e[tot].nxt = hd[u];
	hd[u] = tot;
}
struct node{
	int u,dis;
	node(int a,int b){u=a,dis=b;}
	bool operator>(const node& a)const {
		return dis > a.dis;
	}
};

int dis[MAXN];
bool vis[MAXN];
priority_queue<node, vector<node>, greater<node> >q;
bool dijkstra(int x){
	For(i,1,n) dis[i] = LINF,vis[i] = 0;
	dis[1] = 0;
	while(!q.empty()) q.pop();
	if(f[1] > x) return 0;
	q.push(node(1,0));
	while(!q.empty()){
		int u = q.top().u;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = hd[u];i;i = e[i].nxt){
			int v = e[i].to,w = e[i].w;
			if(f[v] > x) continue;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				q.push(node(v,dis[v]));
			}
		}
	}
	return dis[n] <= b;
}

int r,l;

signed main() {
	IOS;
	cin >> n >> m >> b;
	For(i,1,n){
		cin >> f[i];
		r = max(r,f[i]);
	}
	l = max(f[1],f[n]);
	For(i,1,m){
		int u,v,w;
		cin >> u >> v >> w;
		add(u,v,w);
		add(v,u,w);
	}
	if (!dijkstra(r)) {
		cout << "AFK" << endl;
		return 0;
	}
	while (l < r) {
		int mid = l + ((r - l) >> 1);
		if (dijkstra(mid))
			r = mid;
		else
			l = mid + 1;
	}
	if(dijkstra(l))
		cout << l << endl;
	else cout << "AFK\n";
	return 0;
}