import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int N, K, ans;
	static int[][] map;
	static int[][] horse;
	static List<Integer>[][] list;
	static int[] dx = { 0, 0, 0, -1, 1 };
	static int[] dy = { 0, 1, -1, 0, 0 };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		map = new int[N][N];
		horse = new int[K][3];
		list = new ArrayList[N][N];
		ans = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
				list[i][j] = new ArrayList<>();
			}
		}

		for (int i = 0; i < K; i++) {
			int r = sc.nextInt() - 1;
			int c = sc.nextInt() - 1;
			int dir = sc.nextInt();
			horse[i][0] = r;
			horse[i][1] = c;
			horse[i][2] = dir;
			list[r][c].add(i); // 말번호, 방향
		}
		game(1);
		System.out.println(ans);
	}

	// 0: 흰색, 1: 빨간, 2: 파란
	public static void game(int turn) {
		if (turn > 1000) {
			ans = -1;
			return;
		}
		for (int i = 0; i < K; i++) {
			int[] h = horse[i];
			int r = h[0];
			int c = h[1];
			int dir = h[2];

			int x = r + dx[dir];
			int y = c + dy[dir];

			if (!isRange(x, y) || map[x][y] == 2) {
				if (dir == 1) {
					dir = 2;
				} else if (dir == 2) {
					dir = 1;
				} else if (dir == 3) {
					dir = 4;
				} else if (dir == 4) {
					dir = 3;
				}
				h[2] = dir;
				horse[i] = h;
				x = r + dx[dir];
				y = c + dy[dir];
				if (!isRange(x, y) || map[x][y] == 2) {
					continue;
				} 
			} if (map[x][y] == 0) {
				int idx = -1;
				for (int k = 0; k < list[r][c].size(); k++) {
					int num = list[r][c].get(k);
					if (num == i) {
						idx = k;
						break;
					}
				}
				while (idx < list[r][c].size()) {
					int move = list[r][c].get(idx);
					horse[move][0] = x;
					horse[move][1] = y;
					list[x][y].add(move);
					list[r][c].remove(idx);
				}
				horse[i] = h;
			} else if (map[x][y] == 1) {
				while (true) {
					int size = list[r][c].size();
					int move = list[r][c].get(size - 1);
					horse[move][0] = x;
					horse[move][1] = y;
					list[x][y].add(move);
					list[r][c].remove(size - 1);
					if (move == i)
						break;
				}
			}
			if (list[x][y].size() >= 4) {
				ans = turn;
				return;
			}
		}
		game(turn + 1);
	}

	public static boolean isRange(int r, int c) {
		return r >= 0 && c >= 0 && r < N && c < N;
	}
}