90pts求助，WA on #8

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, b;
int head[10005], cnt;
int dis[10005], a[10005];
bool vis[10005];
struct edge {
	int to, nxt, w;
}e[100005];
void add(int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
queue<int> q;
void spfa(int s) {
	memset(dis, 63, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	while(!q.empty()) q.pop();
	dis[1] = 0;
	vis[1] = 1;
	q.push(1);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = 1;
		for(int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if(a[v] > s) continue;
			if(dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				if(!vis[v]) {
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
}
bool check(int s) {
	if(a[1] > s or a[n] > s) return 0;
	spfa(s);
	return dis[n] <= b;
}
int l, r, ans = -114514, mid;
signed main() {
	cin>>n>>m>>b;
	for(int i = 1; i <= n; i++) {
		cin>>a[i];
		l = a[1];
		l = min(l, a[i]);
		r += a[i];
	}
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		cin>>u>>v>>w;
		add(u, v, w);
		add(v, u, w);
	}
	while(l <= r) {
		mid = (r + l) >> 1;
		if(check(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	if(ans == -114514) cout<<"AFK";
	else cout<<ans;
	return 0;
}