#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long INF=(1ll<<31)-1;
struct node
{
    int to,dis,next;
}edge[10000010];
int n,m,b;
long long d[1000010];
bool vis[1000010];
int f[1000010];
int head[1000010],tot;
void add(int from,int to,int dis)
{
    edge[++tot].to=to;
	edge[tot].dis=dis;
    edge[tot].next=head[from];
    head[from]=tot;
}
bool dijstra(int mid)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    	d[i]=INF;
    d[1]=0;
    priority_queue<pair<long long ,int> >q;
    if(f[1]>mid)
    	return false;
    q.push(make_pair(0,1));
    while(q.size())
    {
        int x=q.top().second;
		q.pop();
        if(vis[x])
			continue;
        vis[x]=1;
        for(int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,dis=edge[i].dis;
            if(d[y]>=d[x]+dis&&f[y]<=mid)
            {
                d[y]=d[x]+dis;
                q.push(make_pair(-d[y],y));
            }           
        }
    } 
	if(d[n]<=b)
		return true;
	return false; 
}
signed main()
{
	cin>>n>>m>>b;
	for(int i=1;i<=n;i++)
		cin>>f[i];
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	int l=0,r=100000010;
	if(!dijstra(r))
	{
		cout<<"AFK";
		return 0;
	}
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(dijstra(mid))
			r=mid;
		else
			l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}

本地TLE