//#define DEBUG_LOCAL
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <ctime>
#define MP make_pair
#define PII pair<int,int>
#define PB push_back
#define SZ(x) (x).size()
#define ld long double
#define ll long long

int MOVE[][2] = {{0, 1},{1, 0},{0, -1},{-1, 0}};

const int timeLimit = (int) (4.5 * CLOCKS_PER_SEC);

inline bool hasTime() {
	return clock() < timeLimit;
}

inline int period() {
	clock_t cl = clock();
	if (cl < timeLimit / 4) return 1;
	if (cl < timeLimit / 2) return 2;
	if (cl < .75*timeLimit) return 3;
	if (cl < timeLimit) return 4;
	return -1;
}

using namespace std;

int n, r, flags2;

#define MAXFLAGS2 32768

int field[128][128];
int finale[128][128];
int tmpFld[128][128];
int bestFlags[MAXFLAGS2];
int flags[MAXFLAGS2];
int curFlags[MAXFLAGS2];
int tmpFlags1[MAXFLAGS2];
int vis[128][128];
int que[32768];
int vec[32768];
int vecE = 0;
inline void vecpb2(int a, int b) {
	vec[vecE++] = a;
	vec[vecE++] = b;
}
int front = 0;
int back = 0;
inline void push2(int a, int b) {
	que[back++] = a;
	que[back++] = b;
}
inline void pop2(int &a, int &b) {
	a = que[front++];
	b = que[front++];
}

inline bool 
	valid(int x, int y, int val) {	 
		return x >= 0 && x < n && y >= 0 && y < n &&
				 !vis[x][y] && 
				 (field[x][y]==val || field[x][y] == 0);
}

bool bfs(int x1, int y1, int reg, int fld[][128]) {
	front = back = 0;
	vecE=0;
	vis[x1][y1] = true;
	int tar = field[x1][y1];
	vecpb2(x1,y1);
	push2(x1,y1);
	int br = 1;
	if (br == tar) goto ok;
	int x, y;
	while (front != back) {
		pop2(x,y);
		for (int i = 0; i < 4; ++i) {
			int nx = x + MOVE[i][0];
			int ny = y + MOVE[i][1];
			if (valid(nx,ny,tar)) {
				push2(nx,ny);
				vis[nx][ny] = true;
				vecpb2(nx,ny);
				if (++br == tar) {
					goto ok;
				}
			}
		}
	}
	goto not_ok;
ok:
	for (int i = 0; i < vecE; i+=2) {
		fld[vec[i]][vec[i+1]] = reg;
	}
	return true;
not_ok:
	return false;
}

void fillField(
			int flags[], int fld[][128]) {
	int sz = r;
	int reg = 1;

	for (int i = 0; i < sz; ++i) {
		int x1 = flags[2*i];
		int y1 = flags[2*i+1];
		if (n < 75) {
			for (int ii = 0; ii < n; ++ii) {
				for (int jj = 0; jj < n; ++jj) {
					vis[ii][jj] = 
						fld[ii][jj] == 0 ? false : true;
				}
			}
		}else {
			memcpy(vis,fld,sizeof(vis));
		}
		if (vis[x1][y1]) continue;
		bool ok = bfs(x1,y1,reg,fld);
		if (ok) reg++;
	}
}


int calc(int flags[]) {
	int res = 0;
	memset(tmpFld,0,sizeof(tmpFld));
	fillField(flags, tmpFld);

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (tmpFld[i][j] != 0) res++;
		}
	}
	return res;
}

void fillFinale(int flags[]) {
	fillField(flags, finale);
}

inline void nxt(int vect[], int maxDist) {
	int sz = r;
	int firstIdx = rand() % (sz-1);
	int add = 1 + rand() % maxDist;
	if (firstIdx + add >= sz) {
		add = sz-firstIdx-1;
	}
	int sndIdx = firstIdx+add;
	int i1 = 2*firstIdx;
	int i2 = 2*firstIdx+1;
	int j1 = 2*sndIdx;
	int j2 = 2*sndIdx+1;
	int tmp1 = vect[i1];
	int tmp2 = vect[i2];
	vect[i1]=vect[j1];
	vect[i2] = vect[j2];
	vect[j1]=tmp1;
	vect[j2]=tmp2;
}

inline ld prob(ld T, ld diff) {
	return exp(diff/T);
}

inline ld prob01() {
	return (ld) rand() / RAND_MAX;
}

inline ld prob02(int pr) {
	if (pr == 1) {
		return rand() / (ld) RAND_MAX * .75;
	} else if (pr == 2) {
		return rand() / (ld) RAND_MAX * .50;
	} else if (pr == 3) {
		return rand() / (ld) RAND_MAX * .25;
	} else {
		return 1e-9;
	}
}

int main() {
	
	srand(1033);

#ifndef DEBUG_LOCAL
	freopen("regions.in", "r", stdin);
#endif
	freopen("regions.out", "w", stdout);
	
	memset(field, 0, sizeof(field));

	int x, y, c;
	scanf("%d %d", &n, &r);
	flags2 = r*2;
	for (int i = 0; i < r; ++i) {
		scanf("%d %d %d", &x, &y, &c);
		x--;y--;
		field[x][y] = c;
		flags[2*i] = x;
		flags[2*i+1] = y;
	}

	int sizeFlags = sizeof(int) * flags2;
	memcpy(bestFlags, flags, sizeFlags);
	int bestSc = calc(flags);
	memcpy(curFlags,flags,sizeFlags);

#ifdef DEBUG_LOCAL
	int iters = 0;
#endif
	ld T = 1000.0;
	ld decr = 0.99;
	ld minTemp = 0.01;
	while (true) {
		int pr = period();
		if (pr == -1) {
			break;
		}
		int maxDist = 
			pr == 1 ? r :
			pr == 2 ? r/2 :
			pr == 3 ? r/4 :
			r / 8;
		maxDist = r;
	   nxt(curFlags, maxDist);
		int curSc = calc(curFlags);
#ifdef DEBUG_LOCAL
		iters++;
#endif
		if (curSc > bestSc) {
			bestSc = curSc;
			memcpy(bestFlags,curFlags,sizeFlags);
		} else {
			if (n>75 || prob01() < prob02(pr)
				//prob(T, curSc - bestSc)
				) {
				memcpy(curFlags,bestFlags,sizeFlags);
			}
		}
		//T *= decr;
	}

#ifdef DEBUG_LOCAL
	cerr << "SCORE: " << bestSc 
		<< " , ITERS: " << iters
		//<< " , T: " << T
		<< endl;
#endif

	memset(finale, 0, sizeof(finale));
	fillFinale(bestFlags);

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			printf("%d%c", finale[i][j], 
				(j < n - 1) ? ' ' : '\n');
		}
	}

	return 0;
}