20pts求条

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Edge{
	int to,dis,next;
}edge[50004];int n,m,b;
int head[60004],vis[50004],d[50004],a[50004];
int cnt; 
void addedge(int from,int to,int dis) {
 	edge[++cnt].next = head[from]; 
 	edge[cnt].dis = dis;
 	edge[cnt].to = to;
 	head[from] = cnt;
}
queue<int>q;
bool spfa(int need) {
	memset(d,0x3f,sizeof(d));
	d[1] = 0;
	vis[1] = 1;
	q.push(1);
	while(!q.empty()) {
		int cur = q.front();
		q.pop(); vis[cur] = 0;
		for(int i = head[cur];i;i = edge[i].next) {
			int toto = edge[i].to;
			if(d[toto] > d[cur] + edge[i].dis) {
				if(a[toto] > need) continue;
				d[toto] = d[cur] + edge[i].dis;
				if(vis[toto] == 0) {
			    	vis[toto] = 1;
			    	q.push(toto);
			    }
			}
		}
	}
	if(d[n] < b) {
		return true;
	}
	return false;
}
signed main() {
	
	cin >> n >> m >> b;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	for(int i = 1;i <= m;i++) {
		int u,v,w;
		cin >> u >> v >> w;
		addedge(u,v,w);
		addedge(v,u,w);
	}
	if(!spfa(1000000000)){
		cout << "AFK" << endl;
		return 0;
	}
	int l = 1,r = 1e9 + 10;
	while(l < r) {
		int mid = (l + r) / 2;
		if(spfa(mid)) {
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	cout << l;
}