/*
ID: espr1t
TASK: Regions
KEYWORDS: NP, Covering
*/

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <ctime>
#include <set>
#include <cassert>

#define RUN_TESTS true
#define DEBUG_INFO false

using namespace std;
FILE* in; FILE* out;

const int MAX = 104;
const int REG = 10004;

struct Cell {
	int row, col;
	Cell(int row_ = 0, int col_ = 0) : row(row_), col(col_) {}
	bool operator < (const Cell& r) const {
		return row != r.row ? row < r.row : col < r.col;
	}
	bool operator == (const Cell& r) const {
		return row == r.row && col == r.col;
	}
};

int n, m, k;
int a[MAX][MAX];
int vis[MAX][MAX], nxtCol;
int dir[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
set <Cell> region[REG];
unsigned sTime;

bool valid(const Cell& cell, int flag) {
	if (cell.row < 0 || cell.row >= n) return false;
	if (cell.col < 0 || cell.col >= m) return false;
	if (vis[cell.row][cell.col]) return false;
	if (a[cell.row][cell.col] != 0 && a[cell.row][cell.col] != flag)
	    return false;
	return true;
}

void bfs(int srow, int scol, int cnt) {
	queue <Cell> q;
	vector <Cell> where;
	q.push(Cell(srow, scol));
	vis[srow][scol] = nxtCol;
	
	while (!q.empty()) {
		Cell cur = q.front(); q.pop();
		where.push_back(cur);
		if ((int)where.size() == cnt)
		    break;
		for (int i = 0; i < 4; i++) {
			Cell nxt(cur.row + dir[i][0], cur.col + dir[i][1]);
			if (valid(nxt, cnt)) {
				if ((int)where.size() + (int)q.size() < cnt) {
					vis[nxt.row][nxt.col] = nxtCol;
					q.push(nxt);
				}
			}
		}
	}
	if ((int)where.size() != cnt) {
		for (int i = 0; i < (int)where.size(); i++) {
			vis[where[i].row][where[i].col] = 0;
		}
	} else {
		for (int i = 0; i < (int)where.size(); i++)
			region[nxtCol].insert(where[i]);
		nxtCol++;
	}
}

void readInput() {
	fscanf(in, "%d %d", &n, &k);
	m = n;
	for (int i = 0; i < k; i++) {
		int row, col, num;
		fscanf(in, "%d %d %d", &row, &col, &num);
		a[row - 1][col - 1] = num;
	}
	fclose(in);
}

void coverGreedily() {
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < m; col++) {
			if (vis[row][col] == 0 && a[row][col] != 0) {
				bfs(row, col, a[row][col]);
			}
		}
	}
}

struct Candidate {
	int size;
	Cell cell;
	Candidate(int size_ = 0, Cell cell_ = Cell()) : size(size_), cell(cell_) {}
	bool operator < (const Candidate& r) const {
		return size > r.size;
	}
};

vector < set<Cell> > neighbors(nxtCol + 1);

Cell findAvailable(int reg) {
	int flag = (int)region[reg].size() + 1;
	for (set <Cell> :: iterator it = region[reg].begin(); it != region[reg].end(); it++) {
		for (int i = 0; i < 4; i++) {
			Cell nxt(it->row + dir[i][0], it->col + dir[i][1]);
			if (valid(nxt, flag))
				return nxt;
		}
	}
	return Cell(-1, -1);
}

void expand(Cell cur, vector<Cell>& cells, int targetCells) {
	if ((int)cells.size() >= targetCells)
	    return;
	cells.push_back(cur);
	vis[cur.row][cur.col] = nxtCol;
	
	for (int i = 0; i < 4; i++) {
		Cell nxt(cur.row + dir[i][0], cur.col + dir[i][1]);
		if (valid(nxt, targetCells)) {
			expand(nxt, cells, targetCells);
		}
	}
}

bool update(int reg, set<Cell>& nbr, vector<Cell>& cells, int targetCells) {
	if (DEBUG_INFO) {
		fprintf(stderr, "    >> Trying to update with neighboring region %d (%d possible cells).\n",
		         reg, (int)neighbors.size());
	}
    int nn[8][2] = {
    	{-1, -1}, {-1, 0}, {-1, +1}, {0, +1},
		{+1, +1}, {+1, 0}, {+1, -1}, {0, -1}
    };
	bool updated = false;
    set <Cell> nnbr;
	for (set<Cell> :: iterator it = nbr.begin(); it != nbr.end(); it++) {
	    Cell remove = *it;
		// No longer part of this region
		if (vis[remove.row][remove.col] != reg) {
			continue;
		}
		/*
		vector <Cell> nnn;
		for (int i = 0; i < 4; i++) {
	    	Cell nxt(remove.row + dir[i][0], remove.col + dir[i][1]);
	    	if (nxt.row < 0 || nxt.row >= n || nxt.col < 0 || nxt.col >= m)
	    	    continue;
	    	if (vis[nxt.row][nxt.col] == reg)
	    	    nnn.push_back(nxt);
		}
		*/
	    vector <bool> has(8, false);
	    for (int i = 0; i < 8; i++) {
	    	Cell nxt(remove.row + nn[i][0], remove.col + nn[i][1]);
	    	if (nxt.row < 0 || nxt.row >= n || nxt.col < 0 || nxt.col >= m)
	    	    continue;
	    	if (vis[nxt.row][nxt.col] == reg)
	    	    has[i] = true;
	    }
	    
	    int cnt = 0;
	    for (int i = 0; i < 8; i++) if (has[i]) {
	    	cnt++;
	    	has[i] = false;
	    	for (int idx = (i + 7) % 8; has[idx]; idx = (idx + 7) % 8)
	    	    has[idx] = false;
	    	for (int idx = (i + 1) % 8; has[idx]; idx = (idx + 1) % 8)
	    	    has[idx] = false;
	    }
	    // If there are two or more components, we cannot remove
	    // the current cell, as this might disconnect the region.
//	    if ((int)nnn.size() == 1) {
		if (cnt <= 1) {
	    	region[reg].erase(remove);
	    	vis[remove.row][remove.col] = nxtCol;
			Cell white = findAvailable(reg);
			vis[remove.row][remove.col] = reg;
			region[reg].insert(remove);
			
			if (white.row != -1) {
				if (DEBUG_INFO) {
					fprintf(stderr, "    -- moving cell (%d, %d) of region %d to cell (%d, %d)\n",
					    remove.row, remove.col, reg, white.row, white.col);
				}
				// Remove toRemove and add white to region reg
				region[reg].erase(remove);
				region[reg].insert(white);
				vis[white.row][white.col] = reg;
				// Add the removed cell to the current region.
				vis[remove.row][remove.col] = nxtCol;
				cells.push_back(remove);
				if (DEBUG_INFO) {
					fprintf(stderr, "    -- adding cell (%d, %d) to currently expanded region.\n",
					    remove.row, remove.col);
				}
				if ((int)cells.size() >= targetCells)
				    return true;
				
				//TODO: test
				// Add new possible neighbors
				for (int i = 0; i < 4; i++) {
					Cell nxt(remove.row + dir[i][0], remove.col + dir[i][1]);
					if (nxt.row < 0 || nxt.row >= n || nxt.col < 0 || nxt.col >= m)
					    continue;
					if (vis[nxt.row][nxt.col] == 0 &&
					        (a[nxt.row][nxt.col] == 0 || a[nxt.row][nxt.col] == targetCells)) {
					    expand(nxt, cells, targetCells);
					}
					else if (vis[nxt.row][nxt.col] != nxtCol &&
					        (a[nxt.row][nxt.col] == 0 || a[nxt.row][nxt.col] == targetCells)) {
					    /*
					    if (vis[nxt.row][nxt.col] == reg) {
					        nnbr.insert(nxt);
					    }
					    */
					    /*
					    if (vis[nxt.row][nxt.col] != reg) {
						    neighbors[vis[nxt.row][nxt.col]].insert(nxt);
					    }
					    */
					}
				}
				updated = true;
			}
	    }
	}
	nbr = nnbr;
	return updated;
}

void tryCandidate(const Candidate& cand) {
	int targetCells = a[cand.cell.row][cand.cell.col];
	assert(targetCells > 0);
	assert(vis[cand.cell.row][cand.cell.col] == 0);

	// Find size of current region
	queue <Cell> q;
	vector <Cell> cells;

	q.push(cand.cell);
	cells.push_back(cand.cell);
	vis[cand.cell.row][cand.cell.col] = nxtCol;
	
	neighbors.clear();
	neighbors.resize(nxtCol + 1);
	
	while (!q.empty()) {
		Cell cur = q.front(); q.pop();
		if ((int)cells.size() >= targetCells)
		    break;

		for (int i = 0; i < 4; i++) {
			Cell nxt(cur.row + dir[i][0], cur.col + dir[i][1]);
			if (nxt.row < 0 || nxt.row >= n || nxt.col < 0 || nxt.col >= m)
			    continue;
			if (vis[nxt.row][nxt.col] != 0 && vis[nxt.row][nxt.col] != nxtCol) {
				if (a[nxt.row][nxt.col] == 0) {
					neighbors[vis[nxt.row][nxt.col]].insert(nxt);
				}
			}
			if (vis[nxt.row][nxt.col] == 0 &&
			        (a[nxt.row][nxt.col] == 0 || a[nxt.row][nxt.col] == targetCells)) {
				if ((int)cells.size() < targetCells) {
					q.push(nxt);
					cells.push_back(nxt);
					vis[nxt.row][nxt.col] = nxtCol;
				}
			}
		}
	}
	if (DEBUG_INFO) {
		fprintf(stderr, "  -- candidate region with size %d which must be %d\n",
		    (int)cells.size(), targetCells);
		fprintf(stderr, "  -- current cells: ");
		for (int i = 0; i < (int)cells.size(); i++)
		    fprintf(stderr, "(%d, %d)%s", cells[i].row, cells[i].col,
				i + 1 == (int)cells.size() ? "\n" : ", ");
	}

	bool updated = true;
	while ((int)cells.size() < targetCells && updated) {
		updated = false;
		for (int reg = 1; reg < nxtCol; reg++) {
			if (!neighbors[reg].empty()) {
			    if (update(reg, neighbors[reg], cells, targetCells)) {
			    	updated = true;
			    	if ((int)cells.size() >= targetCells)
			    	    break;
			    }
			}
		}
	}
	if ((int)cells.size() == targetCells) {
		if (DEBUG_INFO) {
			fprintf(stderr, "  -- expanding a region with size %d.\n", targetCells);
		}
		for (int i = 0; i < (int)cells.size(); i++)
			region[nxtCol].insert(cells[i]);
		assert(region[nxtCol].size() == targetCells);
		nxtCol++;
	} else {
		for (int i = 0; i < (int)cells.size(); i++)
			vis[cells[i].row][cells[i].col] = 0;
	}
}

void makeAnswerBetter() {
	priority_queue <Candidate> q;
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < m; col++) {
			if (a[row][col] != 0 && vis[row][col] == 0) {
				q.push(Candidate(a[row][col], Cell(row, col)));
			}
		}
	}
	while (!q.empty()) {
		Candidate candidate = q.top(); q.pop();
		if (vis[candidate.cell.row][candidate.cell.col] != 0)
		    continue;
		tryCandidate(candidate);
	}
}

void solve() {
	sTime = clock();

	n = m = 0;
	memset(a, 0, sizeof(a));
	nxtCol = 1;
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < REG; i++)
	    region[i].clear();
	
	in = fopen("regions.in", "rt");
	out = fopen("regions.out", "wt");

	readInput();
	coverGreedily();
	makeAnswerBetter();
	
	int score = 0;
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < m; col++) {
			if (vis[row][col] != 0)
			    score++;
			fprintf(out, "%2d%c", vis[row][col], col + 1 == m ? '\n' : ' ');
		}
	}
	fclose(out);
	FILE* tmp = fopen("regions.test", "wt");
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < m; col++) {
			fprintf(tmp, "%2d%c", a[row][col], col + 1 == m ? '\n' : ' ');
		}
	}
	fclose(tmp);
	if (DEBUG_INFO) {
		fprintf(stderr, "  -- score %d.\n", score);
		fprintf(stderr, "  -- execution time: %.3lfs\n",
		    (double)(clock() - sTime) / CLOCKS_PER_SEC);
	}
}

int main(void) {
    solve();
	return 0;