dijkstra

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf = 0x3f3f3f;
const int maxn = 10005;
const int maxm = 1e5 + 5;
int n, m, s, cnt = 0, ans, l = inf, r = -inf;
int val[maxn], dis[maxn], head[maxn];
struct Edge
{
	int nxt, to;
	ll dis;
}edge[maxm];
struct node
{
	int id;
	ll dis;
	bool operator < (const node & s)const
	{
		return s.dis < dis;
	}
};
priority_queue<node>q;

inline ll read()
{
	ll a = 0, f = 1;
	char c = getchar();
	while (!isdigit(c))
	{
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c))
	{
		a = (a << 3) + (a << 1) + (c ^ '0');
		c = getchar();
	}
	return a * f;
}

inline void addedge(int u, int v, int w)
{
	cnt++;
	edge[cnt].nxt = head[u];
	edge[cnt].to = v;
	edge[cnt].dis = w;
	head[u] = cnt;
}

inline int dijkstra(int x)
{
	for (int i = 1; i <= n; i++) dis[i] = inf;
	dis[1] = 0;
	q.push((node) { 1, 0 });
	while (!q.empty())
	{
		node temp = q.top();
		int u = temp.id;
		q.pop();
		if (dis[u] != temp.dis) continue;
		for (int i = head[u]; i; i = edge[i].nxt)
		{
			int v = edge[i].to;
			if (val[v] <= x && dis[u] + edge[i].dis < dis[v])
			{
				dis[v] = dis[u] + edge[i].dis;
				q.push((node) { v, dis[v] });
			}
		}
	}
	if (dis[n] <= s) return 1;
	return 0;
}

int main()
{
	n = read(), m = read(), s = read();
	for (int i = 1; i <= n; i++)
	{
		val[i] = read();
		l = min(l, val[i]);
		r = max(r, val[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		x = read(), y = read(), z = read();
		addedge(x, y, z);
		addedge(y, x, z);
	}
	if (!dijkstra(inf))
	{
		printf("AFK");
		return 0;
	}
	while (l <= r)
	{
		int m=l+r>>1;
		if (dijkstra(m))
		{
			ans = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	printf("%d", ans);
	return 0;
}