WA on #7 #8 #11

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N = 10010;
struct Graph{
	int v , w;
};vector<Graph> g[N];
struct node{
	int ver;
	int distance;
	bool operator < (const node &_) const {
		return _.distance < distance;
	} 
};
int n , m , x , ans = -1;
int f[N];
int dist[N];
int vis[N];
bool dijkstra(int x){
	if(f[1] > x) return false;
	for(int i = 1;i <= n;i++) dist[i] = 1e18;
	memset(vis , 0 , sizeof vis);
	priority_queue<node> q;
	q.push({1 , 0});
	dist[1] = 0LL;
	while(!q.empty()){
		node t = q.top(); q.pop();
		int ver = t.ver , distance = t.distance;
		if(vis[ver]) continue; vis[ver] = 1;
		for(auto it : g[ver]){
			int j = it.v , w = it.w;
			if(f[j] <= x && dist[j] > distance + w){
				dist[j] = distance + w;
				q.push({j , dist[j]});
			}
		}
	}
	return dist[n] <= x;
}
int l = 1 , r = 1000000001;
signed main(){
	cin >> n >> m >> x;
	for(int i = 1;i <= n;i++) cin >> f[i];
	while(m--){
		int u , v , w;
		scanf("%lld%lld%lld" , &u , &v , &w);
		g[u].push_back({v , w});
		g[v].push_back({u , w});
	}
	while(l <= r){   
		int mid = l + r >> 1;
		if(dijkstra(mid)) r = mid - 1 , ans = mid;
		else l = mid + 1; 
	}
	if(ans == -1) puts("AFK");
	else printf("%lld" , ans);
	return 0;
}