#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long tot,n,m,b,l[10002],f[10002];
long long head,tail,team[50002],vis[10002],dis[10002],maxf[10002];
struct node
{
	long long first,next,go,value;
}p[1000004];
void star(long long a,long long b,long long c)
{
	p[++tot].next=p[a].first;
	p[a].first=tot;
	p[tot].go=b;
	p[tot].value=c;
}
void spfa(long long a)
{
	for(long long i=1;i<=n;i++)
	{
		dis[i]=1000000000000;
	}
	dis[a]=maxf[a]=f[a];
	team[++tail]=a;
	while(head<=tail)
	{
		long long x=team[++head];
		vis[x]=0;
		for(long long i=p[x].first;i;i=p[i].next)
		{
			long long y=p[i].value,z=p[i].go;
			if(dis[x]+f[z]<dis[z]&&b>l[x]+y)
			{
				l[z]=l[x]+y;
				dis[z]=dis[x]+f[z];
				cout<<z<<"   "<<l[z]<<" "<<dis[z]<<" ";
				maxf[z]=max(maxf[x],f[z]);
				cout<<maxf[z]<<endl;
				if(!vis[z])
				{
					team[++tail]=z;
					vis[z]=1;
				}
			}
		}
	}
}
int main()
{
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	cin>>n>>m>>b;
	for(long long i=1;i<=n;i++)
	{
		cin>>f[i];
	}
	for(long long i=1;i<=m;i++)
	{
		long long a,b,c;
		cin>>a>>b>>c;
		star(a,b,c);
		star(b,a,c);
	}
	spfa(1);
	cout<<maxf[n]<<endl;
	if(dis[n]==1000000000000)
	cout<<"AFK";
	else
	cout<<maxf[n];
	return 0;
}