#include<cstdio>
#include<vector>
#define N 10005
#define INF 2e+9

using namespace std;

struct node{
	int to,w;
};

vector<node> v[N];
int f[N],tag[N], n,m,b, ans=INF;

void dfs(int u, int s, int now){
	// u为当前节点，s为剩余血量，now为当前路径上交过的最大费用
	
	// 记录到这个结点需要付的费用
	now = f[u]>now?f[u]:now; 
	
	if(u == n){
		ans = now < ans ? now : ans; // 取小的
		return ; 
	} 
	
	// 枚举从u出发的所有边到其他节点 
	int i;
	node tmp; 
	for(i=0;i<v[u].size();i++){
		tmp = v[u][i];
		if(s-tmp.w >= 0 && !tag[tmp.to]){ // 能够经过这条边，并且对应节点没有被访问过 
			tag[tmp.to]=1; // 标记！ 
			dfs(tmp.to,s-tmp.w,now);
			tag[tmp.to]=0; // 回溯后取消标记 
		}
	}
}

int main(void)
{
	int i,j,x,y,z;
	scanf("%d %d %d", &n,&m,&b);
	for(i=1;i<=n;i++)	scanf("%d", f+i);
	for(i=1;i<=m;i++){
		scanf("%d %d %d", &x,&y,&z);
		v[x].push_back(node{y,z});
		v[y].push_back(node{x,z});
	}

	tag[1]=1;
	dfs(1,b,0);
	if(ans != INF)	printf("%d",ans);
	else	printf("AFK");
	return 0;
}