#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e4 + 5;
long long f[N], mxx = -1e9;
vector< pair< int, long long> > g[N]; 
priority_queue< pair< long long, int > > q;
int vis[N], n, m;
long long dis[N], k, v;
int dijkstra(int x)
{
	if(f[1] > x) return 0;
	for(int i = 1; i <= n; i++)
	{
		dis[i] = 1e18;
		vis[i] = 0;
	}
	dis[1] = 0;
	q.push(make_pair(0, 1));
	while(!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = 0; i < g[u].size(); i++)
		{
			int v = g[u][i].first;
			if(f[v] > x) continue; 
			long long w = g[u][i].second;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				q.push(make_pair(-dis[v], v));
				if(v == n)
				{ 
					if(dis[n] >= k) return 0;
					else return 1;
				}	
			}
		}
	}
	return 0;
}

int main()
{
	long long mxx = -1;
	scanf("%d%d%lld", &n, &m, &k);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &f[i]);
		mxx = max(mxx, f[i]); 
	}
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		scanf("%d%d%lld", &x, &y, &v);
		g[x].push_back(make_pair(y, v));
		g[y].push_back(make_pair(x, v));
	}
	long long ans = -1, l = 1, r = mxx;
	while(l <= r)
	{
		long long mid = (l + r) / 2;
		if(dijkstra(mid))
			ans = mid, r = mid - 1;
		else
			l = mid + 1;
	}
	if(ans == -1)
		puts("AFK");
	else
		printf("%lld\n", ans);
	return 0;
}

最后两个点错掉了（subtask#1的12和13）