#include <stdio.h>
#include <string.h>
#include <vector>
#include <stdlib.h>
#include <Windows.h> // for GetTickCount()
using namespace std;

#define FOR(i, n) for (int i = 0; i < int(n); i++)
#define REP(i, vec) for (int i = 0; i < int(vec.size()); i++)
#define FOREACH(x, y) for (int y = 1; y <= n; y++) for (int x = 1; x <= n; x++) 
#ifdef _DEBUG
#	define debugf printf
#else
#	define debugf
#endif

const int TIMELIMIT = 4500;
const int N = 105;

struct Pt {
	int x, y;
	Pt(){}
	Pt(int _x, int _y): x(_x),y(_y){}
};

inline Pt operator + (const Pt& a, const Pt& b)
{
	return Pt(a.x + b.x, a.y + b.y);
}

inline bool operator == (const Pt& a, const Pt& b)
{
	return a.x == b.x && a.y == b.y;
}

const Pt dir[4] = { Pt( -1, 0 ), Pt( 1, 0 ), Pt( 0, -1 ), Pt( 0, 1 ) };

int n;
int a[N][N];
int sol[N][N];
int good[N][N];
int save[N][N];
int bestSol[N][N];
int numTries;
vector<Pt> flags;

unsigned start_clk;

void startTimer() { start_clk = GetTickCount(); }
int timer(void) { return GetTickCount() - start_clk; }

inline bool inrange(int x,int y)
{
	return (x > 0 && x <= n && y > 0 && y <= n);
}

void reset(int arr[N][N])
{
	FOR(y, N) FOR(x, N) arr[y][x] = inrange(x, y) ? 0 : -1;
}

void input()
{
	freopen("regions.in", "rt", stdin);

	int r;
	scanf("%d%d", &n, &r);

	reset(a);
	FOR(i, r) {
		int x, y, c;
		scanf("%d%d%d", &y, &x, &c);
		a[y][x] = c;
		flags.push_back(Pt(x, y));
	}
}

int filled(int arr[N][N])
{
	int res = 00;
	FOREACH(x, y) res += !!arr[y][x];
	return res;
}

void copy(int dest[N][N], int src[N][N])
{
	FOR(y, n + 2)
		FOR(x, n + 2)
			dest[y][x] = src[y][x];
}

inline bool find(const vector<Pt>& v, const Pt& p)
{
	REP(i, v) if (v[i] == p) return true;
	return false;
}

int randFillIter(int color)
{
	int fi;
	FOR(tries, 1000) {
		fi = rand() % flags.size();
		if (!sol[flags[fi].y][flags[fi].x]) break;
	}
	if (sol[flags[fi].y][flags[fi].x]) return 0;
	// random BFS:
	Pt start = flags[fi];
	vector<Pt> state(1, start);
	int regSize = a[start.y][start.x];
	//
	int size = 0;
	while (!state.empty() && size < regSize) {
		size++;
		int idx = rand() % state.size();
		Pt p = state[idx];
		state.erase(state.begin() + idx);
		sol[p.y][p.x] = color;
		FOR(d, 4) {
			Pt np = p + dir[d];
			if (a[np.y][np.x] && a[np.y][np.x] != regSize) continue;
			if (sol[np.y][np.x]) continue;
			if (find(state, np)) continue;
			state.push_back(np);
		}
	}
	if (size == regSize) return size;
	else return 0;
}

int randFill(int color)
{
	// best random fill out of 100 starting attempts:
	copy(save, sol);
	int bestFill = 0;
	FOR(tries, numTries) {
		copy(sol, save);
		int f = randFillIter(color);
		if (f > bestFill) {
			copy(good, sol);
			bestFill = f;
		}
	}
	if (bestFill) 
		copy(sol, good);
	else
		copy(sol, save);
	return bestFill;
}

void solve()
{
	numTries = min(100, 1000 / n);
	reset(bestSol);
	while (timer() < TIMELIMIT) {
		debugf("restart\n");
		reset(sol);
		int unsuccessful = 0;
		int curColor = 1;
		while (timer() < TIMELIMIT && filled(sol) < n*n) {
			int f = randFill(curColor);
			if (f == 0) {
				debugf("randFill null\n");
				if (++unsuccessful > 5) break;
			} else {
				debugf("randFill ok, add = %d with color %d\n", f, curColor);
				unsuccessful = 0;
				curColor++;
			}
		}
		if (filled(sol) > filled(bestSol)) {
			copy(bestSol, sol);
			debugf("new best sol with fill = %d\n", filled(sol));
		}
	}
}

void output()
{
	FILE*f = fopen("regions.out", "wt");
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) {
			if (x > 1) fprintf(f, " ");
			fprintf(f, "%d", bestSol[y][x]);
		}
		fprintf(f, "\n");
	}
	fclose(f);
}


int main(void)
{
	startTimer();
	input();
	solve();
	output();
	return 0;
}