#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, s, dis[N], book[N];

struct node {
	int v, w;
};
vector<node>e[N];

void spfa() {
	for (int i = 1; i <= n; i++) {
		dis[i] = 2147483647;
	}
	dis[s] = 0;
	queue<int>q;
	q.push(s);
	book[s] = 1;
	while (!q.empty()) {
		int tmp = q.front();
		q.pop();
		book[tmp] = 0;
		for (int i = 0; i < e[tmp].size(); i++) {
			int v = e[tmp][i].v;
			int w = e[tmp][i].w;
			if (dis[v] > dis[tmp] + w) {
				dis[v] = dis[tmp] + w;
				if (!book[v]) {
					book[v] = 1;
					q.push(v);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << ' ';
	}
}

void dijkstra() {
	for (int i = 1; i <= n; i++)
		dis[i] = 2147483647;
	dis[s] = 0;
	priority_queue<pair<int, int> >q;
	q.push({0, s});
	while (!q.empty()) {
		int tmp = q.top().second;
		q.pop();
		if(book[tmp])continue;
		book[tmp] = 1;
		for (int i = 0; i < e[tmp].size(); i++) {
			int v = e[tmp][i].v;
			int w = e[tmp][i].w;
			if (dis[v] > dis[tmp] + w) {
				dis[v] = dis[tmp] + w;
				q.push({-dis[v], v});
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << ' ';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
	}
	dijkstra();
	return 0;
}

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

struct node {
	int v, w;
};
int n, m, k, dis[N], book[N];
vector<node>e[N];

void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	priority_queue<pair<int, int>>q;
	q.push({0, 1});
	dis[1] = 0;
	while (!q.empty()) {
		int tmp = q.top().second;
		q.pop();
		if (book[tmp])
			continue;
		book[tmp] = 1;
		for (int i = 0; i < e[tmp].size(); i++) {
			int v = e[tmp][i].v;
			int w = e[tmp][i].w;
			if (dis[v] > max(dis[tmp], w)) {
				dis[v] = max(dis[tmp], w);
				q.push({-dis[v], v});
			}
		}
	}
	int t = k * n + n;
	if (dis[t] == 0x3f3f3f3f)
		dis[t] = -1;
	cout << dis[t] << endl;
}

int main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		e[x].push_back({y, z});
		e[y].push_back({x, z});
		for (int j = 1; j <= k; j++) {
			e[(j - 1)*n + x].push_back({j * n + y, 0});
			e[(j - 1)*n + y].push_back({j * n + x, 0});
			e[j * n + x].push_back({j * n + y, z});
			e[j * n + y].push_back({j * n + x, z});
		}
	}
	dijkstra();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;

int n, m, dis[N][N][2], nxt[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};

struct node {
	int x, y, cost, flag;
	friend bool operator < (node a, node b) {
		return a.cost > b.cost;
	}
};
int mat[N][N];
int sx, sy;

void dijkstra() {
	int res = 1e9;
	priority_queue<node>q;
	q.push({sx, sy, 0, 0});
	memset(dis, 0x3f, sizeof(dis));
	dis[sx][sy][0] = 0;
	while (!q.empty()) {
		node tmp = q.top();
	//	cout << tmp.x << " " << tmp.y << " " << tmp.cost << endl;
		q.pop();
		if (tmp.flag == 1 && mat[tmp.x][tmp.y] == 3 && tmp.cost < res) {
			res = tmp.cost;
		}
		for (int i = 0; i < 4; i++) {
			int nx = tmp.x + nxt[i][0];
			int ny = tmp.y + nxt[i][1];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mat[nx][ny] != 1) {
				//没拿到4且nxny不是4
				int cost = tmp.cost + 1;
				if(tmp.flag==0 && mat[nx][ny]==3)continue;
				if (tmp.flag == 0 && mat[nx][ny] != 4 && dis[nx][ny][0] > cost) {
					dis[nx][ny][0] = cost;
					q.push({nx, ny, cost, 0});
				}
				//没拿到4，且nxny是4
				if (tmp.flag == 0 && mat[nx][ny] == 4 && dis[nx][ny][1] > cost) {
					dis[nx][ny][1] = cost;
					q.push({nx, ny, cost, 1});
				}
				//拿到4
				if (tmp.flag == 1 && dis[nx][ny][1] > cost) {
					dis[nx][ny][1] = cost;
					q.push({nx, ny, cost, 1});
				}
			}
		}
	}
	cout << res << endl;
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
			if (mat[i][j] == 2)
				sx = i, sy = j;
		}
	}
	dijkstra();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n, m, p, k, key[N];

struct edge {
	int v, w, monster;
};
int dis[N][10000];
vector<edge>e[N];

struct node {
	int x, cost, key;
	friend bool operator < (node a, node b) {
		return a.cost > b.cost;
	}
};

void dijkstra() {
	memset(dis, 0x3f, sizeof(dis));
	dis[1][key[1]] = 0;
	priority_queue<node>q;
	q.push({1, 0, key[1]});
	int res = 1e9;
	while (!q.empty()) {
		node tmp = q.top();
		q.pop();
		if (tmp.x == n)
			res = min(res, tmp.cost);
		for (int i = 0; i < e[tmp.x].size(); i++) {
			int v = e[tmp.x][i].v;
			int w = e[tmp.x][i].w;
			int monster = e[tmp.x][i].monster;
			if ((tmp.key | monster) != tmp.key)
				continue;
			int Key = tmp.key | key[v];
			if (dis[v][Key] > tmp.cost + w) {
				dis[v][Key] = tmp.cost + w;
				q.push({v, tmp.cost + w, Key});
			}
		}
	}
	if (res == 1e9)
		res = -1;
	cout << res << endl;
}

int main() {
	cin >> n >> m >> p >> k;
	for (int i = 1; i <= k; i++) {
		int pos, cnt;
		cin >> pos >> cnt;
		while (cnt--) {
			int x;
			cin >> x;
			key[pos] |= (1 << (x - 1));
		}
	}
	for (int i = 1; i <= m; i++) {
		int x, y, z, cnt;
		cin >> x >> y >> z >> cnt;
		int monster = 0;
		while (cnt--) {
			int t;
			cin >> t;
			monster |= (1 << (t - 1));
		}
		e[x].push_back({y, z, monster});
		e[y].push_back({x, z, monster});
	}
	dijkstra();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 15;

int n, m, p, s, k, nxt[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int can[11][11][11][11];
int key[11][11];
int dis[11][11][18000];

struct node {
	int x, y, cost, key;
	friend bool operator < (node a, node b) {
		return a.cost > b.cost;
	}
};

void dijkstra() {
	priority_queue<node>q;
	memset(dis, 0x3f, sizeof(dis));
	dis[1][1][key[1][1]] = 0;
	q.push({1, 1, 0, key[1][1]});
	int res = 1e9;
	while (!q.empty()) {
		node tmp = q.top();
		q.pop();
		if (tmp.x == n && tmp.y == m)
			res = min(res, tmp.cost);
		for (int i = 0; i < 4; i++) {
			int nx = tmp.x + nxt[i][0];
			int ny = tmp.y + nxt[i][1];
			int Key = tmp.key;
			int cost = tmp.cost + 1;
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			if (can[tmp.x][tmp.y][nx][ny] == -1)
				continue;
			if (can[tmp.x][tmp.y][nx][ny] != 0 && (tmp.key & (1 << (can[tmp.x][tmp.y][nx][ny] - 1))) == 0)
				continue;
			Key |= key[nx][ny];
			if (dis[nx][ny][Key] > cost) {
				dis[nx][ny][Key] = cost;
				q.push({nx, ny, cost, Key});
			}
		}
	}
	if (res == 1e9)
		res = -1;
	cout << res << endl;
}

int main() {
	cin >> n >> m >> p >> k;
	for (int i = 1; i <= k; i++) {
		int x1, y1, x2, y2, g;
		cin >> x1 >> y1 >> x2 >> y2 >> g;
		if (g == 0)
			g = -1;
		can[x1][y1][x2][y2] = g;
		can[x2][y2][x1][y1] = g;
	}
	cin >> s;
	for (int i = 1; i <= s; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		key[x][y] |= (1 << (z - 1));
	}
	dijkstra();
	return 0;
}