#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <time.h>
using namespace std;

pair< pair<int,int>,int > Flags[3001];
int r;
int n;

bool Taken[102][102];
bool TFO[102][102];
pair<int,int> q[10002];
int qL;

int Answer[102][102];
int Value[102][102];

int BestAnswer[102][102];
int BestCtr=0;

int TIME_LIMIT=4*CLOCKS_PER_SEC+CLOCKS_PER_SEC/2;

bool TimeIsOK()
{
    if (clock()<TIME_LIMIT)
    return true;
    else
    return false;
}

///Time consume checks
int rem,totaltime=0;

///BFS

inline bool OK(int x,int y,int c)
{
    if (x<1 || x>n || y<1 || y>n)
    return false;
    if (TFO[x][y] || Taken[x][y])
    return false;
    if (Value[x][y]!=c && Value[x][y]!=0)
    return false;

    return true;
}

inline void Add(int x,int y)
{
    qL++;
    q[qL]=make_pair(x,y);
    TFO[x][y]=true;

    return;
}

bool Expand(int x,int y,int c,int reg)
{
    if (Taken[x][y])
    return false;

    int uk=1;
    int i,j;
    int X,Y;
    int ctr=0;

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            TFO[i][j]=false;
        }
    }

    qL=1;
    q[qL]=make_pair(x,y);
    TFO[x][y]=true;

    while(uk<=qL)
    {
        X=q[uk].first;
        Y=q[uk].second;

        Taken[X][Y]=true;
        Answer[X][Y]=reg;

        ctr++;

        if (ctr==c)
        break;

        if (qL>=c)
        {
            uk++;
            continue;
        }

        if (OK(X+1,Y,c))
        Add(X+1,Y);
        if (OK(X-1,Y,c))
        Add(X-1,Y);
        if (OK(X,Y+1,c))
        Add(X,Y+1);
        if (OK(X,Y-1,c))
        Add(X,Y-1);

        uk++;
    }

    for (i=1;i<=qL;i++)
    {
        TFO[ q[i].first ][ q[i].second ]=false;
    }

    if (qL<c)
    {
        for (i=1;i<=qL;i++)
        {
            Taken[ q[i].first ][ q[i].second ]=false;
            Answer[ q[i].first ][ q[i].second ]=0;
        }

        return false;
    }

    return true;
}

///DFS

vector< pair<int,int> > Path;
pair<int,int> order[4];

void DFS(int x,int y,int c)
{
    if (x<1 || x>n || y<1 || y>n)
    return;
    if (Taken[x][y])
    return;
    if (TFO[x][y])
    return;
    if (Value[x][y]!=c && Value[x][y]!=0)
    return;
    if (Path.size()==c)
    return;

    Path.push_back( make_pair(x,y) );
    TFO[x][y]=true;

    DFS(x+order[1].first,y+order[1].second,c);
    DFS(x+order[2].first,y+order[2].second,c);
    DFS(x+order[3].first,y+order[3].second,c);
    DFS(x+order[4].first,y+order[4].second,c);

    return;
}

bool Expand_DFS(int x,int y,int c,int reg)
{
    int i,j;

    /*for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            TFO[i][j]=false;
        }
    }*/

    Path.clear();

    DFS(x,y,c);

    for (i=0;i<Path.size();i++)
    {
        TFO[ Path[i].first ][ Path[i].second ]=false;
    }

    if (Path.size()<c)
    {
        return false;
    }
    else
    {
        for (i=0;i<Path.size();i++)
        {
            Answer[ Path[i].first ][ Path[i].second ]=reg;
            Taken[ Path[i].first ][ Path[i].second ]=true;
        }

        return true;
    }
}

///Print

void PrintAnswer()
{
    int i,j;

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            printf("%d",Answer[i][j]);
            if (j!=n)
            printf(" ");
        }
        printf("\n");
    }

    return;
}

void PrintBestAnswer()
{
    int i,j;

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            printf("%d",BestAnswer[i][j]);
            if (j!=n)
            printf(" ");
        }
        printf("\n");
    }

    return;
}

///Update

void Update()
{
    int i,j;
    int ctr=0;

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (Answer[i][j]>0)
            ctr++;
        }
    }

    if (ctr>BestCtr)
    {
        BestCtr=ctr;

        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
            {
                BestAnswer[i][j]=Answer[i][j];
            }
        }
    }

    return;
}

///Sort functions

bool SF( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.first<b.first.first)
    return true;
    else if (a.first.first>b.first.first)
    return false;
    else
    return a.first.second<b.first.second;
}

bool SF2( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.first>b.first.first)
    return true;
    else if (a.first.first<b.first.first)
    return false;
    else
    return a.first.second<b.first.second;
}

bool SF3( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.first<b.first.first)
    return true;
    else if (a.first.first>b.first.first)
    return false;
    else
    return a.first.second>b.first.second;
}

bool SF4( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.first>b.first.first)
    return true;
    else if (a.first.first<b.first.first)
    return false;
    else
    return a.first.second>b.first.second;
}

bool SF5( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.second<b.first.second)
    return true;
    else if (a.first.second>b.first.second)
    return false;
    else
    return a.first.first<b.first.first;
}

bool SF6( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.second>b.first.second)
    return true;
    else if (a.first.second<b.first.second)
    return false;
    else
    return a.first.first<b.first.first;
}

bool SF7( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.second<b.first.second)
    return true;
    else if (a.first.second>b.first.second)
    return false;
    else
    return a.first.first>b.first.first;
}

bool SF8( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    if (a.first.second>b.first.second)
    return true;
    else if (a.first.second<b.first.second)
    return false;
    else
    return a.first.first>b.first.first;
}

bool SF9( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    return a.first.first<b.first.first;
}

bool SF10( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    return a.first.first>b.first.first;
}

bool SF11( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    return a.first.second<b.first.second;
}

bool SF12( pair< pair<int,int>,int > a, pair< pair<int,int>,int > b )
{
    return a.first.second>b.first.second;
}

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

    int i,j;
    int regctr=0;
    int iter;

    srand(30117);

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

    for (i=1;i<=r;i++)
    {
        scanf("%d %d %d",&Flags[i].first.first,&Flags[i].first.second,&Flags[i].second);

        Value[ Flags[i].first.first ][ Flags[i].first.second ]=Flags[i].second;
    }

    sort(Flags+1,Flags+1+r,SF);

    order[1]=make_pair(-1,0);
    order[2]=make_pair(0,-1);
    order[3]=make_pair(1,0);
    order[4]=make_pair(0,1);

    for (iter=1;;iter++)
    {
        if (!TimeIsOK())
        break;

        if (iter>13)
        random_shuffle(Flags+1,Flags+1+r);
        if (iter==2)
        sort(Flags+1,Flags+1+r,SF2);
        if (iter==3)
        sort(Flags+1,Flags+1+r,SF3);
        if (iter==4)
        sort(Flags+1,Flags+1+r,SF4);
        if (iter==5)
        sort(Flags+1,Flags+1+r,SF5);
        if (iter==6)
        sort(Flags+1,Flags+1+r,SF6);
        if (iter==7)
        sort(Flags+1,Flags+1+r,SF7);
        if (iter==8)
        sort(Flags+1,Flags+1+r,SF8);
        if (iter==9)
        sort(Flags+1,Flags+1+r,SF9);
        if (iter==10)
        sort(Flags+1,Flags+1+r,SF10);
        if (iter==11)
        sort(Flags+1,Flags+1+r,SF11);
        if (iter==12)
        sort(Flags+1,Flags+1+r,SF12);
        if (iter==13)
        sort(Flags+1,Flags+1+r,SF);

        sort(order+1,order+1+4);

        do
        {
            if (!TimeIsOK())
            break;

            if (n>20)
            memset(Taken,false,sizeof(Taken));
            else
            {
                for (i=1;i<=n;i++)
                {
                    for (j=1;j<=n;j++)
                    {
                        Taken[i][j]=false;
                    }
                }
            }
            if (n>20)
            memset(Answer,0,sizeof(Answer));
            else
            {
                for (i=1;i<=n;i++)
                {
                    for (j=1;j<=n;j++)
                    {
                        Answer[i][j]=false;
                    }
                }
            }
            regctr=0;

            for (i=1;i<=r;i++)
            {
                regctr++;
                if (!Expand_DFS(Flags[i].first.first,Flags[i].first.second,Flags[i].second,regctr))
                regctr--;
            }

            Update();
        }while ( next_permutation( order+1,order+1+4 ) );
        ///

        memset(Taken,false,sizeof(Taken));
        memset(Answer,0,sizeof(Answer));
        regctr=0;

        for (i=1;i<=r;i++)
        {
            regctr++;
            if (!Expand(Flags[i].first.first,Flags[i].first.second,Flags[i].second,regctr))
            regctr--;
        }

        Update();
    }

    PrintBestAnswer();
    //fprintf(stderr,"%d iterations made\n",iter);
    //fprintf(stderr,"Best answer = %d\n",BestCtr);
    //fprintf(stderr,"Time spent on the thingy : %d\n",totaltime);

    return 0;