import java.io.*;
import java.util.*;


public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
	static int N, K;
	static final int WHITE = 0;
	static final int RED = 1;
	static final int BLUE = 2;
	static int[] dirRow = {0,0,-1,1};
	static int[] dirCol = {1,-1,0,0};
	static MapInfo[][] map;
	static Chess[] chesses;
	static int turn=0;
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		map = new MapInfo[N+1][N+1];
		chesses = new Chess[K];
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++) {
				int c = Integer.parseInt(st.nextToken());
				map[i][j] = new MapInfo(c,new ArrayList<>());
			}
		}
		
		for(int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken())-1;
			chesses[i] = new Chess(r,c,d);
			map[r][c].state.add(i);
		}
		
		while(true) {
			turn++;
			if(turn >=1000) {
				turn=-1;
				break;
			}
			if(!playTurn()) {
				break;
			};
			
		}
		System.out.println(turn);
	}
	
	private static boolean end() {
		for(Chess chess : chesses) {
			if(map[chess.row][chess.col].state.size()>=4) {
				return true;
			}
		}
		return false;
	}

	private static boolean playTurn() {
		boolean clear= true;
		for(int i=0;i<chesses.length;i++) {
			int row = chesses[i].row;
			int col = chesses[i].col;
			int dir = chesses[i].dir;
			
			int nextRow = row + dirRow[dir];
			int nextCol = col + dirCol[dir];
			
			if(!isRange(nextRow,nextCol)||map[nextRow][nextCol].color==BLUE) {
				chesses[i].dir = changeDir(dir);
				dir = chesses[i].dir;
				nextRow = row + dirRow[dir];
				nextCol = col + dirCol[dir];
				if(!isRange(nextRow,nextCol)||map[nextRow][nextCol].color==BLUE) {
					continue;
				}
			}
			
			if(map[nextRow][nextCol].color==WHITE) {
				//이동할 말들 리스트에 모으기
				List<Integer> moveList = getMoveList(row,col,i);
				//이동시키기//위치정보 갱신//쌓기
				moveToNextPos(nextRow,nextCol,moveList);
			}else if(map[nextRow][nextCol].color==RED) {
				//이동할 말들 정하기
				List<Integer> moveList = getMoveList(row,col,i);
				//이동할 말들 뒤집기
				Collections.reverse(moveList);
				//이동시키기
				//위치정보 갱신
				//말 쌓기 
				moveToNextPos(nextRow,nextCol,moveList);
			}
			if(end()) {
				return false;
			}
			//printMap();
		}
		return true;
	}

	private static void printMap() {
		// TODO Auto-generated method stub
		int idx=0;
		for(Chess c : chesses) {
			System.out.println(idx+" : "+c.toString());
			idx++;
		}
		for(int i=1;i<=N;i++) {
			
			for(int j=1;j<=N;j++) {
				System.out.print("(");
				for(int k :map[i][j].state) {
					System.out.print(k+" ");
				}
				System.out.print(")");
			}
			System.out.println();
		}
	}

	private static void moveToNextPos(int nextRow, int nextCol, List<Integer> moveList) {
		for(int horse:moveList) {
			map[nextRow][nextCol].state.add(horse);
			chesses[horse].row = nextRow;
			chesses[horse].col = nextCol;
		}
	}

	private static List<Integer> getMoveList(int row, int col, int i) {
		List<Integer> list = new ArrayList<>();
		List<Integer> remain = new ArrayList<>();
		boolean move = false;
		for(int horse: map[row][col].state) {
			if(move) {
				list.add(horse);
			}else {
				if(horse == i) {
					move = true;
					list.add(horse);
				}else {
					remain.add(horse);
				}
			}
		}
		
		map[row][col].state = remain;
		 
		return list;
	}

	private static int changeDir(int dir) {
		return (dir%2==0)?dir+1:dir-1;
	}

	private static boolean isRange(int nextRow, int nextCol) {
		return nextRow>=1 && nextCol>=1 && nextRow <=N && nextCol <=N;
	}

	static class MapInfo{
		int color;
		List<Integer> state;
		public MapInfo(int color, List<Integer> state) {
			this.color = color;
			this.state = state;
		}
		
	}
	
	static class Chess{
		int row,col,dir;

		public Chess(int row, int col, int dir) {
			this.row = row;
			this.col = col;
			this.dir = dir;
		}

		@Override
		public String toString() {
			return "Chess [row=" + row + ", col=" + col + ", dir=" + dir + "]";
		}
		
	}
}