#include <iostream>
#include <cstdio>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <time.h>
#define TLM 4700
using namespace std;
typedef int lld;

struct Awesome
{
    lld x, y, val;

    bool operator<(const Awesome& other)const
    {
        return (val < other.val);
    }
};
Awesome GetA(lld x, lld y, lld val)
{
    Awesome ret;
    ret.x = x;
    ret.y = y;
    ret.val = val;
    return ret;
}

struct QWE
{
    lld x, y, qval;

    bool operator<(const QWE& other)const
    {
        return (qval < other.qval);
    }
};
QWE GetQ(lld x, lld y)
{
    QWE ret;
    ret.x = x; ret.y = y;ret.qval = rand();
    return ret;
}

lld coolx[4] = {1, -1, 0, 0}, cooly[4] = {0, 0, 1, -1};

lld n, r;
lld init[102][102], grid[102][102];
lld conwithG[102][102], conwithC[10002], comp[102][102], ccnt;
bool taken[102][102];

lld tlm = TLM * CLOCKS_PER_SEC / 1000;

bool HaveTime()
{
    return (clock() < tlm);
}

bool Valid(lld x, lld y)
{
    return (x >= 1 && x <= n && y >= 1 && y <= n);
}

void Input()
{
    scanf("%d %d", &n, &r);
    for (lld i=1; i<=r; i++)
    {
        lld x, y, c;

        scanf("%d %d %d", &x, &y, &c);
        init[x][y] = c;
        grid[x][y] = c;
    }
}

lld father[10002];
lld fsv[10002], fcw[10002];
lld cans[10002], current=0, final[10002];


lld Evaluate(lld cans[10002])
{
    lld ret = 0;

    for (lld i=1; i<=n; i++)
    {
        for (lld j=1; j<=n; j++)
        {
            ret += (cans[comp[i][j]] != 0);
        }
    }

    return ret;
}

void SaveAnswer()
{
    for (lld i=0; i<10002; i++)
    {
        final[i] = cans[i];
    }
}
bool CheckAnswer()
{
    lld newone = Evaluate(cans);

    if (newone > current)
    {
        SaveAnswer();
        current = newone;
    }
}


void SaveFather()
{
    for (lld i=1; i<=ccnt; i++)
    {
        fsv[i] = father[i];
        fcw[i] = conwithC[i];
    }
}
void RestoreFather()
{
    for (lld i=1; i<=ccnt; i++)
    {
        father[i] = fsv[i];
        conwithC[i] = fcw[i];
    }
}


lld Find(lld node)
{
    if (father[node] == 0) return node;

    lld root = Find(father[node]);
    father[node] = root;
    return root;
}
bool Union(lld v1, lld v2)
{
    lld r1 = Find(v1), r2 = Find(v2);
    if (r1 == r2) return false;

    father[r1] = r2;
    conwithC[r2] += conwithC[r1];
    return true;
}


bool TFO[102][102];
bool compused[10002];
bool compforbidden[10002];

lld GetInComponent(lld nx, lld ny)
{
    lld curc = comp[nx][ny];
    return conwithC[Find(curc)];
}

lld ord[4];
priority_queue<QWE> q;
bool BFS_Fill(lld bx, lld by, lld acnt)
{
    QWE cur;
    lld done = 0, indr=0, lookfor = grid[bx][by];
    vector<QWE> toclear;

    q = priority_queue<QWE>();
    memset(TFO, 0, sizeof(TFO));
    memset(compused, 0, sizeof(compused));
    SaveFather();
    lld times=0;

    cur = GetQ(bx, by);

    if (compforbidden[ comp[bx][by] ]) return false;


    TFO[cur.x][cur.y] = true;
    q.push( GetQ(cur.x, cur.y) );

    toclear.push_back( cur );
    grid[cur.x][cur.y] = lookfor;
    taken[cur.x][cur.y] = true;

    compused[ comp[cur.x][cur.y] ] = true;
    done = GetInComponent(cur.x, cur.y);
    cans[ comp[cur.x][cur.y] ] = acnt;

    while (!q.empty())
    {
        cur = q.top();
        q.pop();

        if (done == lookfor)
        {
            for (lld i=0; i<toclear.size(); i++)
            {
                lld x=toclear[i].x, y=toclear[i].y;
                compforbidden[ comp[x][y] ] = true;
            }

            return true;
        }

        random_shuffle(ord, ord+4);
        bool putfront = rand()&1;

        for (lld i=0; i<4; i++)
        {
            lld nx = cur.x+coolx[ord[i]], ny = cur.y+cooly[ord[i]];
            if (!Valid(nx, ny)) continue;
            if (TFO[nx][ny] || taken[nx][ny] || (grid[nx][ny] != 0 && grid[nx][ny] != lookfor)) continue;
            if (compforbidden[ comp[nx][ny] ]) continue;

            lld nxt = done;
            if (!compused[ comp[nx][ny] ])
            {
                nxt += GetInComponent(nx, ny);
            }
            if (nxt > lookfor) continue;

            if (!compused[ comp[nx][ny] ])
            {
                Union(comp[cur.x][cur.y], comp[nx][ny]);
                compused[ comp[nx][ny] ] = true;
            }

            cans [comp[nx][ny]] = acnt;
            done = nxt;

            q.push( GetQ(nx, ny) );

            TFO[nx][ny] = true;

            toclear.push_back( GetQ(nx, ny) );
            grid[nx][ny] = lookfor;
            taken[nx][ny] = true;


            if (done == lookfor)
            {
                for (lld i=0; i<toclear.size(); i++)
                {
                    lld x=toclear[i].x, y=toclear[i].y;
                    compforbidden[ comp[x][y] ] = true;
                    cans [comp[x][y]] = acnt;
                }

                return true;
            }
        }
    }

    RestoreFather();
    for (lld i=0; i<toclear.size(); i++)
    {
        lld x = toclear[i].x, y = toclear[i].y;

        cans[ comp[x][y] ] = 0;
        grid[x][y] = init[x][y];
        taken[x][y] = false;
    }

    return false;
}


bool BFS_Fill_WithoutBullshit(lld bx, lld by, lld acnt)
{
    QWE cur;
    lld done = 0, indr=0, lookfor = grid[bx][by];
    vector<QWE> toclear;

    q = priority_queue<QWE>();
    memset(TFO, 0, sizeof(TFO));
    memset(compused, 0, sizeof(compused));
    SaveFather();
    lld times=0;

    cur = GetQ(bx, by);

    if (compforbidden[ comp[bx][by] ]) return false;


    TFO[cur.x][cur.y] = true;
    q.push( GetQ(cur.x, cur.y) );

    toclear.push_back( cur );
    grid[cur.x][cur.y] = lookfor;
    taken[cur.x][cur.y] = true;

    compused[ comp[cur.x][cur.y] ] = true;
    done = GetInComponent(cur.x, cur.y);
    cans[ comp[cur.x][cur.y] ] = acnt;

    while (!q.empty())
    {
        cur = q.top();
        q.pop();

        if (done == lookfor)
        {
            for (lld i=0; i<toclear.size(); i++)
            {
                lld x=toclear[i].x, y=toclear[i].y;
                compforbidden[ comp[x][y] ] = true;
            }

            return true;
        }

        random_shuffle(ord, ord+4);
        bool putfront = rand()&1;

        for (lld i=0; i<4; i++)
        {
            lld nx = cur.x+coolx[ord[i]], ny = cur.y+cooly[ord[i]];
            if (!Valid(nx, ny)) continue;
            if (TFO[nx][ny] || taken[nx][ny] || grid[nx][ny] != 0) continue;
            if (compforbidden[ comp[nx][ny] ]) continue;

            lld nxt = done;
            if (!compused[ comp[nx][ny] ])
            {
                nxt += GetInComponent(nx, ny);
            }
            if (nxt > lookfor) continue;

            if (!compused[ comp[nx][ny] ])
            {
                Union(comp[cur.x][cur.y], comp[nx][ny]);
                compused[ comp[nx][ny] ] = true;
            }

            cans [comp[nx][ny]] = acnt;
            done = nxt;

            q.push( GetQ(nx, ny) );

            TFO[nx][ny] = true;

            toclear.push_back( GetQ(nx, ny) );
            grid[nx][ny] = lookfor;
            taken[nx][ny] = true;


            if (done == lookfor)
            {
                for (lld i=0; i<toclear.size(); i++)
                {
                    lld x=toclear[i].x, y=toclear[i].y;
                    compforbidden[ comp[x][y] ] = true;
                    cans [comp[x][y]] = acnt;
                }

                return true;
            }
        }
    }

    RestoreFather();
    for (lld i=0; i<toclear.size(); i++)
    {
        lld x = toclear[i].x, y = toclear[i].y;

        cans[ comp[x][y] ] = 0;
        grid[x][y] = init[x][y];
        taken[x][y] = false;
    }

    return false;
}

lld Count(lld x, lld y)
{
    lld ret = 1;

    TFO[x][y] = true;
    for (lld i=0; i<4; i++)
    {
        lld nx = x+coolx[i], ny = y+cooly[i];
        if (!Valid(nx, ny) || TFO[nx][ny] || grid[nx][ny] != grid[x][y]) continue;

        TFO[nx][ny] = true;
        ret += Count(nx, ny);
    }

    return ret;
}
void Write(lld x, lld y, lld res, lld cm, bool onetime = false)
{
    conwithG[x][y] = res;
    comp[x][y] = cm;
    conwithC[cm] = res;

    TFO[x][y] = true;

    if (onetime) return;

    for (lld i=0; i<4; i++)
    {
        lld nx = x+coolx[i], ny = y+cooly[i];
        if (!Valid(nx, ny) || TFO[nx][ny] || grid[nx][ny] != grid[x][y]) continue;

        TFO[nx][ny] = true;
        Write(nx, ny, res, cm);
    }
}

vector< Awesome > all;
void BFSADVANCE()
{
    lld cnt = 1;

    for (lld i=0; i<all.size(); i++)
    {
        if (!HaveTime()) break;

        lld x=all[i].x, y=all[i].y;
        if (taken[x][y]) continue;

        if (!BFS_Fill_WithoutBullshit(x, y, cnt))
        {
            if (BFS_Fill( x, y, cnt)) cnt++;
        }
        else cnt++;

    }
}


void Print()
{
    for (lld i=1; i<=n; i++)
    {
        for (lld j=1; j<=n; j++)
        {
            printf("%d", final[comp[i][j]]);

            if (j == n) printf("\n");
            else printf(" ");
        }
    }
}


void RollBack()
{
    memset(TFO, 0, sizeof(TFO));
    memset(conwithG, 0, sizeof(conwithG));
    memset(conwithC, 0, sizeof(conwithC));
    memset(cans, 0, sizeof(cans));
    memset(taken, 0, sizeof(taken));
    memset(comp, 0, sizeof(comp));
    memset(compforbidden, 0, sizeof(compforbidden));
    memset(compused, 0, sizeof(compused));
    memset(father, 0, sizeof(father));
    memset(grid, 0, sizeof(grid));
    ccnt = 0;
    for (lld i=1; i<=n; i++)
    {
        for (lld j=1; j<=n; j++)
        {
            grid[i][j] = init[i][j];
        }
    }
}

int main ()
{
    srand(22335577);

    freopen("regions.in", "r", stdin);
    freopen("regions.out", "w", stdout);

    for (lld i=0; i<4; i++)
    {
        ord[i] = i;
    }


    Input();

    for (lld i=1; i<=n; i++)
    {
        for (lld j=1; j<=n; j++)
        {
            if (grid[i][j] == 0) continue;

            all.push_back( GetA(i, j, grid[i][j]) );
        }
    }

    lld tcnt=0;
    do
    {
        tcnt++;
        RollBack();
        memset(TFO, 0, sizeof(TFO));
        for (lld i=1; i<=n; i++)
        {
            for (lld j=1; j<=n; j++)
            {
                if (TFO[i][j] || grid[i][j] == 0) continue;

                lld res = Count(i, j);
                conwithG[i][j] = res;
            }
        }

        memset(TFO, 0, sizeof(TFO));
        for (lld i=1; i<=n; i++)
        {
            for (lld j=1; j<=n; j++)
            {
                if (TFO[i][j]) continue;

                if (conwithG[i][j] == 0)
                {
                    Write(i, j, 1, ++ccnt, true);
                }
                else
                {
                    Write(i, j, conwithG[i][j], ++ccnt);
                }
            }
        }

        BFSADVANCE();
        CheckAnswer();
        random_shuffle(all.begin(), all.end());
    }
    while (HaveTime());

   // cout<<"Tested "<<tcnt<<" times\n";
   // cout<<Evaluate(final)<<"\n";
    Print();
}