#include <cstdio>
#include <iostream>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <ctime>

using namespace std;

#define FOR(a,n) for(int a=0; a<n; ++a)
#define FORREV(a,n) for(int a=n-1; a>=0; --a)
#define FOR2(a,from,to) for(int a=from; a<=to; ++a)
#define FOR2REV(a,from,to) for(int a=to; a>=from; --a)

#define MAXN 100
#define MAXC 10000

FILE *fout=fopen("regions.out", "w");

int dx[4]={+1,-1, 0, 0};
int dy[4]={ 0, 0,+1,-1};

int N,C;
int fx[MAXC],fy[MAXC];
int flag[MAXN][MAXN];

int sorted[MAXC];
bool compareFlags(int a, int b) { return (flag[fy[a]][fx[a]] < flag[fy[b]][fx[b]] ); }
bool compareFlags2(int a, int b) { return (flag[fy[a]][fx[a]] > flag[fy[b]][fx[b]] ); }

void init()
{
	scanf("%d %d", &N, &C);
	
	int x,y,n;
	FOR(i,C) { scanf("%d %d %d", &fy[i], &fx[i], &n); --fy[i]; --fx[i]; flag[fy[i]][fx[i]]=n; }
	FOR(i,C) sorted[i]=i;
}

//action 1: create region at flag

int region[MAXN][MAXN];

bool u[MAXN][MAXN];
bool v[MAXN][MAXN];

int stX[MAXN*MAXN],stY[MAXN*MAXN],stN=0;
void stAdd(int x, int y) { stX[stN]=x; stY[stN]=y; ++stN; }

int createRegion(int y, int x, int reg[][MAXN], int &num)
{
	//O(N^2)
	
	// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	FOR(i,N) memset(u[i], 0, N);
	//FOR(i,N) FOR(j,N) u[i][j]=false;
	stN=0;
	
	queue<int> qx,qy;
	qx.push(x); qy.push(y);
	u[y][x] = 1;
	
	int newY,newX;
	
	int n=flag[y][x];
	
	while(1)
	{
		if(qx.empty()) break;
		x=qx.front(); qx.pop();
		y=qy.front(); qy.pop();
		
		stAdd(x,y);
		if(stN == n) break;
		
		FOR(i,4)
		{
			newX = x+dx[i];
			newY = y+dy[i];
			if(newY>=0 and newY<N and newX>=0 and newX<N and !u[newY][newX] and !reg[newY][newX] and (flag[newY][newX]==n or !flag[newY][newX]))
			{
				qx.push(newX); qy.push(newY);
				u[newY][newX] = 1;
			}
		}
	}
	
	if(stN == n)
	{
		FOR(i,stN) reg[stY[i]][stX[i]] = num;
		++num;
		return stN;
	}
	return 0;
}


int solve()
{
	FOR(i,N) memset(region[i], 0, N*sizeof(region[0][0]));
	int cnt=0;
	int nextRegion=1;
	int x,y;
	FOR(i,C)
	{
		x=fx[sorted[i]]; y=fy[sorted[i]];
		if(!region[y][x]) cnt += createRegion(y,x,region,nextRegion);
		if(clock() > 4900) break;
	}
	return cnt;
}

int bestSol[MAXN][MAXN];
int bestScore=0;

int getRand(int from, int to) { return from + (to - from + 1); }

void randomize(int a[], int n)
{
	int idx2;
	FOR(i,n)
	{
		FOR(j,(rand()&7)+1)
		{
			idx2 = getRand(i, n-1);
			if(idx2 != i) swap(a[i], a[idx2]);
		}
	}
}

int main()
{
	freopen("regions.in", "r", stdin);
	//freopen("regions.out", "w", stdout);
	
	init();
	
	int t;
	
	t = solve();
	if(t > bestScore) FOR(i,N) FOR(j,N) bestSol[i][j]=region[i][j];
	
	sort(sorted,sorted+C, compareFlags);
	t = solve();
	if(t > bestScore) FOR(i,N) FOR(j,N) bestSol[i][j]=region[i][j];
	
	sort(sorted,sorted+C, compareFlags2);
	t = solve();
	if(t > bestScore) FOR(i,N) FOR(j,N) bestSol[i][j]=region[i][j];
	
	while(clock() < 4800)
	{
		randomize(sorted,C);
		t = solve();
		if(t > bestScore) FOR(i,N) FOR(j,N) bestSol[i][j]=region[i][j];
	}
	
	
	FOR(i,N)
	{
		FOR(j,N) fprintf(fout, "%d ", bestSol[i][j]);
		fprintf(fout, "\n");
	}
	
	
	
	return 0;
}