#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;


int N;
int R;
int T[100][100];
vector<int> Fx, Fy;

vector< vector<pair<int, int> > > Regions;

void read_input() {
    ifstream F;
    F.open("regions.in");
    F >> N >> R;
    memset(T, 0, sizeof(T));
    for(int i = 0; i < R; i++) {
        int x, y, c;
        F >> y >> x >> c;
        x--;
        y--;
        T[x][y] = c;
        Fx.push_back(x);
        Fy.push_back(y);
    }
    F.close();
}


int SOL[100][100];
int K;
void init_sol() {
    Regions.resize(1);
    K = 0;
    memset(SOL, 0, sizeof(SOL));
}

void print_sol() {
  ofstream F;
  F.open("regions.out");
    for(int y = 0; y < N; y++) {
        for(int x = 0; x < N; x++)
           F << SOL[x][y] << " ";
        F << endl;
    }
    F.close();
}





int V[100][100];
int Tx[10000], Ty[10000];

bool possible(int x, int y, int f) {
    return (x >= 0 && y >= 0 && x < N && y < N && !V[x][y] && (T[x][y] == f || T[x][y] == 0) && SOL[x][y] == 0);
}


int free_space(int x, int y, int max) {

    int target = T[x][y];
    memset(V, 0, sizeof(V));
    Tx[0] = x;
    Ty[0] = y;
    int a = 0;
    int b = 1;
    V[x][y] = 1;

    while(a < b && b < max) {
        int x0 = Tx[a];
        int y0 = Ty[a];
        a++;

       if(possible(x0, y0-1, target)) {
           Tx[b] = x0;
           Ty[b] = y0-1;
           V[x0][y0-1] = 1;
           b++;
           if(b == max) break;
        }
        if(possible(x0 - 1, y0, target)) {
           Tx[b] = x0-1;
           Ty[b] = y0;
           V[x0-1][y0] = 1;
           b++;
           if(b == max) break;
        }
       if(possible(x0 + 1, y0, target)) {
           Tx[b] = x0+1;
           Ty[b] = y0;
           V[x0+1][y0] = 1;
           b++;
           if(b == max) break;
        }
       if(possible(x0, y0+1, target)) {
           Tx[b] = x0;
           Ty[b] = y0+1;
           V[x0][y0+1] = 1;
           b++;
           if(b == max) break;
        }
    }
    return b;

}


void add_sol(int nb) {
       K++;
       vector< pair<int,int> > RR;
       for(int i = 0; i < nb; i++) {
            SOL[Tx[i]][Ty[i]] = K;
            RR.push_back(make_pair(Tx[i],Ty[i]));
        }
        Regions.push_back(RR);
}

void find_region(int x, int y) {
    int target = T[x][y];
    int nb = free_space(x, y, target);
 //   cerr << x << " " << y << " " << nb << " " << target << endl;
    if(nb == target) add_sol(nb);
}


int TMP[100][100];

vector<pair<int,int> > border(const vector<pair<int,int> > & RR) {
    memset(TMP, 0, sizeof(TMP));
    for(int i = 0; i < RR.size(); i++)
        TMP[RR[i].first][RR[i].second] = 1;
    vector<pair<int,int> > Ret;
    for(int i = 0; i < RR.size(); i++) {
        int x = RR[i].first;
        int y = RR[i].second;
    //cerr << "BORDER " << RR.size() << " " << x << " " << y << " " << Ret.size() << endl;
        if(x > 0 && SOL[x-1][y] == 0 && TMP[x-1][y] == 0) Ret.push_back(make_pair(x-1, y));
        if(x+1 < N && SOL[x+1][y] == 0 && TMP[x+1][y] == 0) Ret.push_back(make_pair(x+1, y));
        if(y > 0 && SOL[x][y-1] == 0 && TMP[x][y-1] == 0) Ret.push_back(make_pair(x, y-1));
        if(y+1 < N && SOL[x][y+1] == 0 && TMP[x][y+1] == 0) Ret.push_back(make_pair(x, y+1));
    }
    return Ret;
}

vector<pair<int,int> > border(int k) {
    return border(Regions[k]);
}





void swap(int x1, int y1, int x2, int y2) {
    int k = SOL[x1][y1];
    SOL[x2][y2] = k;
    SOL[x1][y1] = 0;
    for(int i = 0; i < Regions[k].size(); i++)
        if(Regions[k][i].first == x1 && Regions[k][i].second == y1) {
            Regions[k][i].first = x2;
            Regions[k][i].second = y2;
        }
}




int V2[100][100];
int T2x[10000], T2y[10000];

bool possible2(int x, int y) {
    return (x >= 0 && y >= 0 && x < N && y < N && V2[x][y] == 2);
}

bool connected(const vector<pair<int,int> > & RR) {
    if(RR.size() == 0) return false;
    memset(V2, 0, sizeof(V2));
    for(int i = 0; i < RR.size(); i++) V2[RR[i].first][RR[i].second] = 2;
    V2[RR[0].first][RR[0].second] = 1;
    T2x[0] = RR[0].first;
    T2y[0] = RR[0].second;
    int a = 0;
    int b = 1;

    while(a < b) {
        int x0 = T2x[a];
        int y0 = T2y[a];
        a++;

       if(possible2(x0, y0-1)) {
           T2x[b] = x0;
           T2y[b] = y0-1;
           V2[x0][y0-1] = 1;
           b++;
        }
        if(possible2(x0 - 1, y0)) {
           T2x[b] = x0-1;
           T2y[b] = y0;
           V2[x0-1][y0] = 1;
           b++;
        }
       if(possible2(x0 + 1, y0)) {
           T2x[b] = x0+1;
           T2y[b] = y0;
           V2[x0+1][y0] = 1;
           b++;
        }
       if(possible2(x0, y0+1)) {
           T2x[b] = x0;
           T2y[b] = y0+1;
           V2[x0][y0+1] = 1;
           b++;
        }
    }
    return b == RR.size();

}



bool try_expand_1(int x, int y, int sz) {
/*
    cerr << "SOL " << sz << " ";
    for(int i =0 ; i < sz; i++) cerr << Tx[i] << " " << Ty[i] << " | ";
    cerr << endl;
*/

    if(T[x][y] != 0) return false;

    int k = SOL[x][y];
    vector<pair<int,int> > Reg = Regions[k];
        for(int i = 0; i < Reg.size(); i++) if(Reg[i].first == x && Reg[i].second == y) {
            Reg[i] = Reg.back();
            Reg.pop_back();
        }
 /*   cerr << "bubu " ;
        for(int i =0 ; i < Reg.size(); i++) cerr << Reg[i].first << " " <<Reg[i].second << " | ";
    cerr << endl;
*/
    if(!connected(Reg)) return false;


    if( k == 0) cerr << "ERROR1" << endl;
    vector<pair<int, int> > B = border(Reg);

  /*  cerr << "TE1 " << x << " " << y << " " << sz << " " << B.size() << " " << Regions[k].size() << " " << k << endl;
    for(int i = 0; i < B.size(); i++) cerr << B[i].first << " " << B[i].second << " | ";
    cerr << endl;
*/
    for(int i = 0; i < B.size(); i++) {
        int nx = B[i].first;
        int ny = B[i].second;
        if(V[nx][ny] == 0 && SOL[nx][ny] == 0 && (T[nx][ny] == 0 || T[nx][ny] == Regions[k].size())) { // TODO check sol = size
      //      cerr << "HEHE " << x << " " << y << " " << nx << " " << ny << " " << k << endl;
      //      cerr << "HEHE " << x << " " << y << " " << nx << " " << ny << " " << k << endl;
            swap(x, y, nx, ny);
            V[x][y] = 1;
            Tx[sz] = x;
            Ty[sz] = y;
            return true;
        };
    }
    return false;
}

int try_expand(int sz, int target) {
    for(int i = 0; i < sz; i++) {
        int x = Tx[i];
        int y = Ty[i];
 //       cerr << "TE0 " << x << " " << y << " " << target << " " << sz << endl;
        if(x > 0 && V[x-1][y] == 0)
            if(try_expand_1(x-1, y, sz)) sz++;
        if(sz == target) break;
        if(x+1 < N && V[x+1][y] == 0)
            if(try_expand_1(x+1, y, sz)) sz++;
        if(sz == target) break;
        if(y > 0 && V[x][y-1] == 0)
            if(try_expand_1(x, y-1, sz)) sz++;
        if(sz == target) break;
        if(y+1 < N && V[x][y+1] == 0)
            if(try_expand_1(x, y+1, sz)) sz++;
        if(sz == target) break;
    }
    return sz;
}


bool split(int k) {

    int nb_ok = 0;
    for(int i = 0; i < Regions[k].size(); i++)if(T[Regions[k][i].first][Regions[k][i].second] != 0) nb_ok++;
    if(nb_ok <= 1) return false;

    for(int i = 0; i < Regions[k].size(); i++) if(T[Regions[k][i].first][Regions[k][i].second] != 0) {
        int x = Regions[k][i].first;
        int y = Regions[k][i].second;
     vector<pair<int,int> > Reg = Regions[k];
     Reg.erase(Reg.begin() + i);
     if(!connected(Reg)) continue;
     vector<pair<int, int> > B = border(Reg);
        for(int i = 0; i < B.size(); i++) {
        int nx = B[i].first;
        int ny = B[i].second;
        if(SOL[nx][ny] == 0 && (T[nx][ny] == 0 || T[nx][ny] == Regions[k].size())) {
            swap(x, y, nx, ny);
            return true;
        }
    }
    }
    return false;
}


int main() {
    read_input();
    init_sol();

  /*  vector<pair<int, int> > order;
    for(int i = 0; i < R; i++)
        order.push_back(make_pair(T[Fx[i]][Fy[i]], i));

    sort(order.begin(), order.end());
    for(int i = 0; i < order.size(); i++) {
        int x = Fx[order[i].second];
        int y = Fy[order[i].second];
        if(T[x][y] != 0 && SOL[x][y] == 0)
            find_region(x,y);
        cerr << x << " " << y << endl;
            }
    */

     for(int y = 0; y < N; y++)
        for(int x = 0; x < N; x++)
            if(T[x][y] != 0 && SOL[x][y] == 0)
                find_region(x,y);


    bool good = true;
    while(good) {
        good = false;
        for(int i = 0; i < Fx.size(); i++) {
            if(SOL[Fx[i]][Fy[i]] == 0) {
                int target = T[Fx[i]][Fy[i]];
                int nb = free_space(Fx[i],Fy[i], N*N);
                cerr << Fx[i] << " " << Fy[i] << " " << T[Fx[i]][Fy[i]] << " " << nb << endl;
                int sz = try_expand(nb, target);
                if (sz == target) {
                    add_sol(sz);
                    cerr << "YAAA " << sz << " " << K << endl;
                    good = true;
                }
            }
        }
        for(int k = 1; k <= K; k++) split(k);
    }


    print_sol();
    return 0;