#define CRT_SECURE_NO_DEPRECATE
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <iomanip>
#include <string>
#include <cmath>
#include <sstream>
#include <iostream>
#include <ctime>

#define all(x) x.begin(), x.end()

typedef long long ll;
typedef long double ld;
const ld eps = 1e-9;
const ld time_bomb = 4.5;
using namespace std;

const string PROBLEM_NAME = "regions";

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

ld START_TIME;

ld get_time() {
	return double(clock())/CLOCKS_PER_SEC;
}

int answer[128][128];
pair<int, int> vis[12000];
int vis_size;
void finish_up(const vector<vector<int> >& a, const vector<pair<int,int> >& flags,
	const vector<int>& order, int &total, int&  last_used) {
		int n = (int)a.size();
		int r = (int)flags.size();
		int number = 1;
		total = 0;
		// vector<vector<int> > ans(n, vector<int>(n, 0));
		memset(answer, 0, sizeof(answer));
		
		for (int iter = 0; iter < (int)order.size(); ++iter) {
			if (get_time() - START_TIME > time_bomb) {
				break;
			}
			int idx = order[iter];
			if (answer[flags[idx].first][flags[idx].second] != 0) {
				continue;
			}
			vis_size = 0;
			vis[vis_size++] = flags[idx];
			queue<pair<int, int> > q;
			queue<pair<int, int> > same;
			same.push(flags[idx]);
			answer[flags[idx].first][flags[idx].second] = -1;
			while((!q.empty() || !same.empty()) && vis_size < a[flags[idx].first][flags[idx].second]) {
				pair<int, int> cur;
				if (!same.empty()) {
					cur = same.front();
					same.pop();
				} else {
					cur = q.front();
					q.pop();
				}
				int st = rand() % 4 ;
				for (int lt = 0; lt < 4; ++lt) {
					int l  = (lt + st) % 4;
					int tx = cur.first + moves[l][0];
					int ty = cur.second + moves[l][1];

					if (tx < 0 || ty < 0 || tx >= n || ty >= n) {
						continue;
					}
					if ((a[tx][ty] != 0 && a[tx][ty] != a[flags[idx].first][flags[idx].second]) || answer[tx][ty] != 0) {
						continue;
					}
					vis[vis_size].first = tx;
					vis[vis_size].second = ty;
					vis_size++;
					if (a[tx][ty] == a[flags[idx].first][flags[idx].second]) {
						same.push(vis[vis_size-1]);
					} else {
						q.push(vis[vis_size-1]);
					}
					answer[tx][ty] = -1;
				}
			}

			if (vis_size < a[flags[idx].first][flags[idx].second]) {
				for (int i = 0; i < vis_size; ++i) {
					answer[vis[i].first][vis[i].second] = 0;
				}
				continue;
			}
			for (int i =  0; i < a[flags[idx].first][flags[idx].second]; ++i) {
				answer[vis[i].first][vis[i].second] = number;
				total++;
			}
			for (int i = a[flags[idx].first][flags[idx].second]; i < vis_size; ++i) {
				answer[vis[i].first][vis[i].second] = 0;
			}
			last_used = iter;
			number++;
		}
}

void finish_up2(const vector<vector<int> >& a, const vector<pair<int,int> >& flags,
	const vector<int>& order, const vector<vector<int> >& ans, int removed, int &total, int&  last_used) {
		int n = (int)a.size();
		int r = (int)flags.size();
		int number = removed;
		total = 0;
		// vector<vector<int> > ans(n, vector<int>(n, 0));
		int biggest = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				answer[i][j] = ans[i][j];
				if (ans[i][j] == removed) {
					answer[i][j] = 0;
				}
				biggest = max(biggest, answer[i][j]);
				if (answer[i][j] != 0) {
					total++;
				}
			}
		}

		for (int iter = 0; iter < (int)order.size(); ++iter) {
			if (get_time() - START_TIME > time_bomb) {
				break;
			}
			int idx = order[iter];
			if (answer[flags[idx].first][flags[idx].second] != 0) {
				continue;
			}
			vis_size = 0;
			vis[vis_size++] = flags[idx];
			queue<pair<int, int> > q;
			queue<pair<int, int> > same;
			same.push(flags[idx]);
			answer[flags[idx].first][flags[idx].second] = -1;
			while((!q.empty() || !same.empty()) && vis_size < a[flags[idx].first][flags[idx].second]) {
				pair<int, int> cur;
				if (!same.empty()) {
					cur = same.front();
					same.pop();
				} else {
					cur = q.front();
					q.pop();
				}
				int st = rand() % 4 ;
				for (int lt = 0; lt < 4; ++lt) {
					int l  = (lt + st) % 4;
					int tx = cur.first + moves[l][0];
					int ty = cur.second + moves[l][1];

					if (tx < 0 || ty < 0 || tx >= n || ty >= n) {
						continue;
					}
					if ((a[tx][ty] != 0 && a[tx][ty] != a[flags[idx].first][flags[idx].second]) || answer[tx][ty] != 0) {
						continue;
					}
					vis[vis_size].first = tx;
					vis[vis_size].second = ty;
					vis_size++;
					if (a[tx][ty] == a[flags[idx].first][flags[idx].second]) {
						same.push(vis[vis_size-1]);
					} else {
						q.push(vis[vis_size-1]);
					}
					answer[tx][ty] = -1;
				}
			}

			if (vis_size < a[flags[idx].first][flags[idx].second]) {
				for (int i = 0; i < vis_size; ++i) {
					answer[vis[i].first][vis[i].second] = 0;
				}
				continue;
			}
			for (int i =  0; i < a[flags[idx].first][flags[idx].second]; ++i) {
				answer[vis[i].first][vis[i].second] = number;
				total++;
			}
			for (int i = a[flags[idx].first][flags[idx].second]; i < vis_size; ++i) {
				answer[vis[i].first][vis[i].second] = 0;
			}
			last_used = iter;
			if (number == removed) {
				number = biggest + 1;
			} else {
				number++;
			}
		}
}

vector<vector<int> > solve_random(const vector<vector<int> >& a, const vector<pair<int,int> >& flags) {
	int n = (int)a.size();
	int r = (int)flags.size();
	vector<int> order(r);


	vector<pair<int, int> > help(r);

	int btotal = 0;
	vector<vector<int> > ba;

	for (int i =0 ; i < r; ++i ) {
		help[i].second = i;
		help[i].first = a[flags[i].first][flags[i].second];
	}
	sort(all(help));
	// reverse(all(help));
	for (int i =0 ; i < r; ++i ) {
		order[i] = help[i].second;
	}
	// random_shuffle(all(order));


	int total, last_used;
	vector<vector<int> > ans(n, vector<int>(n, 0));

	finish_up(a, flags, order, total, last_used);
	for (int i = 0; i < n; ++i) {
		for (int j  = 0 ; j < n;++j) {
			ans[i][j] = answer[i][j];
		}
	}

	if (last_used < 1 ) {
		return ans;
	}

	while (get_time() - START_TIME < time_bomb) {
		for (int i = 0; i < n; ++i) {
			order[i] = i;
		}

		random_shuffle(all(order));
		int ctotal, clast_used;
		finish_up(a, flags, order, ctotal, clast_used);
		if (ctotal > total) {
			total = ctotal;
			last_used = clast_used;

			for (int ih = 0; ih < n; ++ih) {
				for (int jh  = 0 ; jh < n;++jh) {
					ans[ih][jh] = answer[ih][jh];
				}
			}
		}
	}

	return ans;
}

vector<vector<int> > solve_random_optimize(const vector<vector<int> >& a, const vector<pair<int,int> >& flags) {
	int n = (int)a.size();
	int r = (int)flags.size();
	vector<int> order(r);


	vector<pair<int, int> > help(r);

	for (int i =0 ; i < r; ++i ) {
		help[i].second = i;
		help[i].first = a[flags[i].first][flags[i].second];
	}
	sort(all(help));
	// reverse(all(help));
	for (int i =0 ; i < r; ++i ) {
		order[i] = help[i].second;
	}
	// random_shuffle(all(order));


	int total, last_used;


	vector<vector<int> > ans(n, vector<int>(n, 0));

	finish_up(a, flags, order, total, last_used);
	for (int i = 0; i < n; ++i) {
		for (int j  = 0 ; j < n;++j) {
			ans[i][j] = answer[i][j];
		}
	}

	if (last_used < 1 ) {
		return ans;
	}

	while (get_time() - START_TIME < time_bomb) {

		int i = rand() % last_used;
		if (ans[flags[order[i]].first][flags[order[i]].second] == 0) {
			continue;
		}
		int j = rand() % r;
		while (j == i) {
			j = rand() % r;
		}
		swap(order[i], order[j]);
		int ctotal, clast_used;
		finish_up(a, flags, order, ctotal, clast_used);
		if (ctotal > total) {
			total = ctotal;
			last_used = clast_used;
			for (int ih = 0; ih < n; ++ih) {
				for (int jh  = 0 ; jh < n;++jh) {
					ans[ih][jh] = answer[ih][jh];
				}
			}

		} else {
			swap(order[i], order[j]);
		}
	}

	return ans;
}


vector<vector<int> > solve_greedy_optimize(const vector<vector<int> >& a, const vector<pair<int,int> >& flags) {
	int n = (int)a.size();
	int r = (int)flags.size();

	vector<vector<int> > help2(n, vector<int>(n, 0));
	memset(answer, 0, sizeof(answer));
	for (int i = 0; i < n; ++i) {
		for (int j  = 0; j < n; ++j) {
			if (a[i][j] == 0) {
				continue;
			}
			if (help2[i][j] != 0 || answer[i][j] != 0) {
				continue;
			}
			answer[i][j] = 1;
			vis_size = 0;
			vis[vis_size++] = make_pair(i, j);
			int visi = 0;
			while(vis_size > visi) {
				pair<int,int> cur = vis[visi];
				visi++;
				for (int l = 0; l < 4; ++l) {
					int tx = cur.first + moves[l][0];
					int ty = cur.second + moves[l][1];

					if (tx < 0 || ty < 0 || tx >= n || ty >= n) {
						continue;
					}
					if (a[tx][ty] != a[i][j] || answer[tx][ty] != 0) {
						continue;
					}
					vis[vis_size].first = tx;
					vis[vis_size].second = ty;
					vis_size++;
					answer[tx][ty] = 1;
				}
			}
			for (int k = 0; k < vis_size; ++k) {
				help2[vis[k].first][vis[k].second] = vis_size;
			}
		}
	}

	vector<int> order(r);

	vector<pair<pair<int, int>, int> > help(r);

	for (int i =0 ; i < r; ++i ) {
		help[i].second = i;
		help[i].first = make_pair(a[flags[i].first][flags[i].second] - help2[flags[i].first][flags[i].second],
			a[flags[i].first][flags[i].second]);
	}

	sort(all(help));
	// reverse(all(help));
	for (int i =0 ; i < r; ++i ) {
		order[i] = help[i].second;
	}
	// random_shuffle(all(order));


	int total, last_used;


	vector<vector<int> > ans(n, vector<int>(n, 0));

	finish_up(a, flags, order, total, last_used);
	for (int i = 0; i < n; ++i) {
		for (int j  = 0 ; j < n;++j) {
			ans[i][j] = answer[i][j];
		}
	}

	if (last_used < 1 ) {
		return ans;
	}

	while (get_time() - START_TIME < time_bomb) {

		int i = rand() % last_used;
		if (ans[flags[order[i]].first][flags[order[i]].second] == 0) {
			continue;
		}
		int j = rand() % r;
		while (j == i) {
			j = rand() % r;
		}
		swap(order[i], order[j]);
		int ctotal, clast_used;
		finish_up(a, flags, order, ctotal, clast_used);
		if (ctotal > total) {
			total = ctotal;
			last_used = clast_used;
			for (int ih = 0; ih < n; ++ih) {
				for (int jh  = 0 ; jh < n;++jh) {
					ans[ih][jh] = answer[ih][jh];
				}
			}

		} else {
			swap(order[i], order[j]);
		}
	}

	return ans;
}


vector<vector<int> > solve_fast_greedy_optimize(const vector<vector<int> >& a, const vector<pair<int,int> >& flags) {
	int n = (int)a.size();
	int r = (int)flags.size();

	vector<vector<int> > help2(n, vector<int>(n, 0));
	memset(answer, 0, sizeof(answer));
	for (int i = 0; i < n; ++i) {
		for (int j  = 0; j < n; ++j) {
			if (a[i][j] == 0) {
				continue;
			}
			if (help2[i][j] != 0 || answer[i][j] != 0) {
				continue;
			}
			answer[i][j] = 1;
			vis_size = 0;
			vis[vis_size++] = make_pair(i, j);
			int visi = 0;
			while(vis_size > visi) {
				pair<int,int> cur = vis[visi];
				visi++;
				for (int l = 0; l < 4; ++l) {
					int tx = cur.first + moves[l][0];
					int ty = cur.second + moves[l][1];

					if (tx < 0 || ty < 0 || tx >= n || ty >= n) {
						continue;
					}
					if (a[tx][ty] != a[i][j] || answer[tx][ty] != 0) {
						continue;
					}
					vis[vis_size].first = tx;
					vis[vis_size].second = ty;
					vis_size++;
					answer[tx][ty] = 1;
				}
			}
			for (int k = 0; k < vis_size; ++k) {
				help2[vis[k].first][vis[k].second] = vis_size;
			}
		}
	}

	vector<int> order(r);

	vector<pair<pair<int, int>, int> > help(r);

	for (int i =0 ; i < r; ++i ) {
		help[i].second = i;
		help[i].first = make_pair(a[flags[i].first][flags[i].second] - help2[flags[i].first][flags[i].second],
			a[flags[i].first][flags[i].second]);
	}

	sort(all(help));
	// reverse(all(help));
	for (int i =0 ; i < r; ++i ) {
		order[i] = help[i].second;
	}
	// random_shuffle(all(order));


	int total, last_used;


	vector<vector<int> > ans(n, vector<int>(n, 0));

	finish_up(a, flags, order, total, last_used);
	for (int i = 0; i < n; ++i) {
		for (int j  = 0 ; j < n;++j) {
			ans[i][j] = answer[i][j];
		}
	}

	if (last_used < 1 ) {
		return ans;
	}

	while (get_time() - START_TIME < time_bomb) {
		int i = rand() % last_used;
		int ctotal, clast_used;
		finish_up2(a, flags, order, ans, i, ctotal, clast_used);
		if (ctotal > total) {
			total = ctotal;
			last_used = clast_used;
			for (int ih = 0; ih < n; ++ih) {
				for (int j  = 0 ; j < n;++j) {
					ans[ih][j] = answer[ih][j];
				}
			}

		}
	}

	return ans;


}

vector<vector<int> > solve_trivial(const vector<vector<int> >& a, const vector<pair<int,int> >& flags) {
	int n = (int)a.size();

	vector<vector<int> > ans(n, vector<int>(n, 0));
	int number = 1;
	for (int i =0 ; i < n; ++i){ 
		for (int j = 0; j <n; ++j) {
			if (a[i][j] == 1) {
				ans[i][j] = number++;
			}
		}
	}
	return ans;
}


vector<vector<int> > solve(const vector<vector<int> >& a, const vector<pair<int,int> >& flags) {
	srand(43);
	if ((int)a.size() >= 75) {
		return solve_fast_greedy_optimize(a, flags);
	} else {
		return solve_greedy_optimize(a, flags);
	}
}

void optimize(vector<vector<int> >& a, vector<pair<int,int> >& flags) {
	int n = (int)a.size();
	for (int idx = 0; idx < (int)flags.size(); ++idx) {
		vector<pair<int, int> > vis;
		vis.push_back(flags[idx]);
		queue<pair<int, int> > q;
		q.push(flags[idx]);
		int val = a[flags[idx].first][flags[idx].second];
		a[flags[idx].first][flags[idx].second] = -2;

		while(!q.empty() && vis.size() < a[flags[idx].first][flags[idx].second]) {
			pair<int, int> cur = q.front();
			q.pop();
			for (int l = 0; l < 4; ++l) {
				int tx = cur.first + moves[l][0];
				int ty = cur.second + moves[l][1];

				if (tx < 0 || ty < 0 || tx >= n || ty >= n) {
					continue;
				}
				if ((a[tx][ty] != 0 && a[tx][ty] != val)) {
					continue;
				}
				vis.push_back(make_pair(tx, ty));
				q.push(vis.back());
				if (a[tx][ty] == val) {
					a[tx][ty] = -2;
				} else {
					a[tx][ty] = -1;
				}
			}
		}
		for (int i = 0; i < (int)vis.size(); ++i) {
			if (a[vis[i].first][vis[i].second] == -1) {
				a[vis[i].first][vis[i].second] = 0;
			} else {
				a[vis[i].first][vis[i].second] = val;
			}
		}
		if ((int)vis.size() < a[flags[idx].first][flags[idx].second]) {
			swap(flags[idx], flags[(int)flags.size() - 1]);
			flags.pop_back();
			idx--;
		}
	}
}

int main() {
	freopen((PROBLEM_NAME + ".in").c_str(), "r", stdin);
	freopen((PROBLEM_NAME + ".out").c_str(), "w", stdout);

	START_TIME = get_time();
	vector<vector<int> > a;
	int n;

	int r;
	scanf("%d %d", &n, &r);
	a.clear();
	a.resize(n, vector<int>(n, 0));

	vector<pair<int, int> > flags(r);
	for (int i = 0; i < r; ++i) {
		int t;
		scanf("%d %d %d", &flags[i].first, &flags[i].second, &t);
		flags[i].first--;
		flags[i].second--;
		a[flags[i].first][flags[i].second] = t;
	}

	optimize(a, flags);
	vector<vector<int> > result = solve(a, flags);
	for (int i = 0; i < n; ++i ) {
		for (int j = 0; j < n; ++j) {
			printf("%d%c", result[i][j], " \n"[j + 1== n]);
		}
	}
	return 0;