#include<bits/stdc++.h>
#include<climits>
using namespace std;

int edgecnt=0, h[200050];
int n, m;
long long b, fy[200050];
long long dis[200050];
bool dict[200050];
long long inf = LLONG_MAX/3;
long long l, r, mid;

struct Edge
{
	long long w;
	int to, next;
}edge[200050];

struct Node
{
	long long w;
	int pos;
	friend bool operator < (const Node &x, const Node &y)
	{
		return x.w > y.w;
	}
};

priority_queue<Node> q;

void addedge(int u, int v, long long w)
{
	edge[++edgecnt].to = v;
	edge[edgecnt].w = w;
	edge[edgecnt].next = h[u];
	h[u] = edgecnt;
}

void dijkstra(int fylm)
{
	for (int i = 1; i <= n; i++){
		dict[i] = 0; dis[i] = inf;
	}
	dis[1] = 0;
	while (!q.empty()) q.pop();
	q.push((Node) {0, 1});
	while (!q.empty())
	{
		Node zxtmp = q.top();
		q.pop();
		long long expa = zxtmp.pos;
		if (dict[expa]) continue;
		dict[expa] = 1;
		for (int i = h[expa]; i != -1; i = edge[i].next){
			if (fy[edge[i].to] > fylm) continue;
			if (dis[edge[i].to] > dis[expa]+edge[i].w){
				dis[edge[i].to] = dis[expa]+edge[i].w;
				q.push((Node) {dis[edge[i].to], edge[i].to});
			}
		}
	}
}

int main()
{
	scanf("%d%d%lld", &n, &m, &b);
	for (int i = 0; i <= n; i++) h[i] = -1;
	for (int i = 1; i <= n; i++){
		scanf("%lld", &fy[i]); r = max(r, fy[i]);
	}
	l = max(fy[1], fy[n]);
	int u, v;
	long long w;
	for (int i = 0; i <= m-1; i++){
		scanf("%d%d%lld", &u, &v, &w);
		addedge(u, v, w); addedge(v, u, w);
	}
	while (l < r)
	{
		mid = (l+r)/2;
		dijkstra(mid);
		if (dis[n] > b) l = mid+1;
		else r = mid;
	}
	dijkstra(1);
	if (dis[n] > b) printf("%lld", l);
	else printf("AFK");
	return 0;
}

测试点 subtask0:#1,#4,#7 / subtask1:#11 WA

求助qwq