#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>

int n,m,hp;
vector<pa > v[10010];
int d[10010];
int used[10010];
int f[10010];
priority_queue< pa,vector<pa>,greater<pa > > q; 
bool dij(int limit){
	for (int i = 1; i <= n ; i ++ ) d[i]= 2e9;
	d[1]=0;
	q.push(make_pair(0,1));
	while (q.size()) {
		pa dt = q.top(); q.pop();
		int x = dt.second;
		if (used[x]) continue;
		used[x]=1;
		for (int i = 0 ; i < v[x].size(); i ++ ) {
			int y = v[x][i].first,z = v[x][i].second;
			if (f[y]>limit) continue;
			if (d[x]+z<d[y]) {
				d[y]=d[x]+z;
				q.push(make_pair(d[y],y));
			}
		}
	}
	return d[n]<=hp;
}
int main() {
	cin>>n>>m>>hp;
	int l = 0 , r = 0;
	for (int i = 1; i <= n ; i ++ ) cin>>f[i],r = max(r, f[i]);
	for (int i = 1; i <= m ; i ++ ) {
		int a,b,c;
		cin>>a>>b>>c;
		v[a].push_back(make_pair(b,c));
		v[b].push_back(make_pair(a,c));
	}
	if (!dij(r)) {
		cout<<"AFK"<<endl;
		return 0;
	}
	while (l<r) {
		int mid = (l+r)/2;
		if (dij(mid)) r = mid;
		else l = mid + 1;
	}
	cout<<l<<endl;
	return 0;
}

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

const int maxn = 5000 + 10;

int head[maxn],nxt[maxn<<1],to[maxn<<1],v[maxn<<1];
int dis[maxn],used[maxn],sum[maxn];
//sum[i] 表示到达i点的经过了多少条边 
int n,m,cnt;
void add(int a,int b,int c) {
	nxt[++cnt]=head[a];
	head[a]=cnt;
	to[cnt]=b;
	v[cnt]=c;
}
void init() {
	memset(head,0,sizeof(head));
	memset(nxt,0,sizeof(nxt));
	cin>>n>>m;
	for (int i = 1; i <= m ; i ++ ) {
		int a,b,c;
		cin>>a>>b>>c;
		add(b,a,c);
	}
}
bool spfa() {
	for(int i = 1; i <= n ; i ++ ) dis[i]=2147483647;
	dis[1]=0;
	memset(sum,0,sizeof(sum));
	memset(used,0,sizeof(used));
	queue<int> q;
	for (int i = 1; i <= n ; i ++ ) {
		q.push(i);
		used[i]=true;
	}
	while (q.size()) {
		int x = q.front();
		q.pop();
		used[x]=false;
		if (dis[x]==2147483647) dis[x]=0;
		for (int i = head[x];i;i=nxt[i]) {
			int y = to[i], z = v[i];
			if (dis[x]+z<dis[y]) {
				dis[y]=dis[x]+z;
				sum[y]=sum[x]+1;
				if (sum[y]==n) return true;
				if (!used[y]) {
					used[y]=true;
					q.push(y);
				}
			}
		}
	} 
	for (int i= 1; i <= n ; i ++ ) cout<<dis[i]<<' ';
	return false;
}
int main(){
	init();
	if (spfa()) puts("NO");
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 +10;

int n,m;
vector<int> v[maxn];
int used[maxn],ans;//foot[i] 代表到达i这个点的最短路
int foot[maxn];
int ji[maxn],ou[maxn];
void bfs(int x) {
	//第一步，将初始状态放入队列
	queue<pair<int,int> > q;
	for (int i = 1 ; i <= n ; i ++ ) ji[i]=ou[i]=0x7fffffff;
	for (int i = 0 ; i < v[1].size() ; i ++ ) {
		ji[v[1][i]]=1;
		q.push(make_pair(v[1][i],1));
	}
	while (q.size()) {
		int x = q.front().first,z=q.front().second;q.pop();//取队头
		for (int i = 0 ; i <  v[x].size() ;i ++ ) {//枚举每一条从x出发的边
			int y = v[x][i];
			if (z%2==0) {
				if (z+1<ji[y]) {
					ji[y]=z+1;
					q.push(make_pair(y,z+1));
				}
			}else {
				if (z+1<ou[y]) {
					ou[y]=z+1;
					q.push(make_pair(y,z+1));
				}
			}
		}
	}

}
int main() {
	int q;
	cin>>n>>m>>q;
	for (int i = 1; i <= m ; i ++ ) {
		int a,b,c;
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	bfs(1);
	while (q--) {
		int x,L;
		scanf("%d%d",&x,&L);
		if (L%2==0) {
			if (ou[x]<=L) puts("Yes");
			else puts("No");
		} else {
			if (ji[x]<=L) puts("Yes");
			else puts("No");
		}
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,a,b;
vector<int> g[1001];
int dis[1010];
int bfs(int s) {
	deque<int> dq;
	memset(dis,0x3f3f3f3f,sizeof dis);
	dis[s]=0;
	dq.push_front(s);//从头部插入
	while (dq.size()) {
		int x = dq.front();
		dq.pop_front();//从头部pop
		if (g[x].size()==0) continue;
		int y = g[x][0];
		if (x==b) return dis[b];
		if (dis[y]>dis[x]){
			dis[y]=dis[x];
			dq.push_front(y);//插入到前排 
		}
		for(int k = 1 ; k < g[x].size(); k ++ ) {
			int y = g[x][k];
			if (dis[y]>dis[x]+1) {
				dis[y]=dis[x]+1;
				dq.push_back(y);//尾部插入 
			}
		} 
	} 
	return -1; 
} 
int main(){
	cin>>n>>a>>b;
	for (int i = 1; i <= n ; i ++ ) {
		int k;
		cin>>k;
		for (int j = 1; j <= k ; j ++ ) {
			int x;cin>>x;
			g[i].push_back(x);
		}
	}
	cout<<bfs(a)<<endl;
  return 0;
}