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

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

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

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

		for (int i = 0; i < K; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			int dir = sc.nextInt() - 1;
			horse[i][0] = x;
			horse[i][1] = y;
			horse[i][2] = dir;
			game[x][y].add(i);
		}

		move(1);
		System.out.println(ans);
	}

	public static void move(int turn) {
		if (turn > 1000) {
			ans = -1;
			return;
		}
		for (int i = 0; i < K; i++) {
			int x = horse[i][0];
			int y = horse[i][1];
			int dir = horse[i][2];
			
			int idx = game[x][y].indexOf(i);
			if (idx != 0)
				continue;

			int r = x + dx[dir];
			int c = y + dy[dir];
			if (!isRange(r, c) || map[r][c] == 2) {
				if (dir == 0)
					dir = 1;
				else if (dir == 1)
					dir = 0;
				else if (dir == 2)
					dir = 3;
				else if (dir == 3)
					dir = 2;
				horse[i][2] = dir;
				r = x + dx[dir];
				c = y + dy[dir];
				if (!isRange(r, c) || map[r][c] == 2)
					continue;
			}

			if (map[r][c] == 0) {
				for (int j = idx; j < game[x][y].size();) {
					int num = game[x][y].get(j);
					horse[num][0] = r;
					horse[num][1] = c;
					game[r][c].add(num);
					game[x][y].remove(j);
				}
			} else if (map[r][c] == 1) {
				int size = game[x][y].size() - 1;
				for (int j = size; j >= idx; j--) {
					int num = game[x][y].get(j);
					horse[num][0] = r;
					horse[num][1] = c;
					game[r][c].add(num);
					game[x][y].remove(j);
				}
			}

			if (game[r][c].size() >= 4) {
				ans = turn;
				return;
			}
		}

		move(turn + 1);
	}

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