#include<iostream>
#include<fstream>
#include<vector>
#include<ctime>
#include<queue>
using namespace std;
ofstream fout ("regions.out");
  ifstream fin ("regions.in");

int ASD=24;

struct st
{
    int x,y,z;
};
struct Comp
{
    bool operator()(const st& a,const st& b)
    {
        return a.z<b.z;
    }
};
struct Comp2
{
    bool operator()(const st& a,const st& b)
    {
        return a.z>b.z;
    }
};
struct Comp3
{
    bool operator()(const st& a,const st& b)
    {
        return (a.x+a.y+a.z)>(b.x+b.y+b.z);
    }
};
struct Comp4
{
    bool operator()(const st& a,const st& b)
    {
        return (42*a.z+a.x*13+a.y*666)%1024>(42*b.z+b.x*13+b.y*666)%1024;
    }
};
struct Comp5
{
    bool operator()(const st& a,const st& b)
    {
        return (42*a.z+a.x*13+a.y*666)%1024<(42*b.z+b.x*13+b.y*666)%1024;
    }
};
struct Comp6
{
    bool operator()(const st& a,const st& b)
    {
        return (a.x+a.y+a.z)<(b.x+b.y+b.z);
    }
};
struct Comp7
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*42/(a.x*a.y)>b.z*42/(b.x*b.y);
    }
};
struct Comp8
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*42/(a.x*a.y)<b.z*42/(b.x*b.y);
    }
};
struct Comp9
{
    bool operator()(const st& a,const st& b)
    {
        return (a.z*42/(a.x*a.y))%2<(b.z*42/(b.x*b.y))%2;
    }
};
struct Comp10
{
    bool operator()(const st& a,const st& b)
    {
        return (a.z*42/(a.x*a.y))%2>(b.z*42/(b.x*b.y))%2;
    }
};
struct Comp11
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*b.x<b.z*a.y;
    }
};
struct Comp12
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*b.x>b.z*a.y;
    }
};
struct Comp13
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*454+a.x*546+a.y*102<b.z*454+b.x*546+b.y*102;
    }
};
struct Comp14
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*454+a.x*546+a.y*102>b.z*454+b.x*546+b.y*102;
    }
};
struct Comp15
{
    bool operator()(const st& a,const st& b)
    {
        return (a.z*781/a.x*a.y)%666<(b.z*781/b.x*b.y)%666;
    }
};
struct Comp16
{
    bool operator()(const st& a,const st& b)
    {
        return (a.z*781/a.x*a.y)%666>(b.z*781/b.x*b.y)%666;
    }
};
struct Comp17
{
    bool operator()(const st& a,const st& b)
    {
        return a.z%7<b.z%7;
    }
};
struct Comp18
{
    bool operator()(const st& a,const st& b)
    {
        return a.z%7>b.z%7;
    }
};
struct Comp19
{
    bool operator()(const st& a,const st& b)
    {
        return a.z/3*54*a.x/13*a.y/5*19<b.z/3*54*b.x/13*b.y/5*19;
    }
};
struct Comp20
{
    bool operator()(const st& a,const st& b)
    {
        return a.z/3*54*a.x/13*a.y/5*19>b.z/3*54*b.x/13*b.y/5*19;
    }
};
struct Comp21
{
    bool operator()(const st& a,const st& b)
    {
        return a.z/3*54*a.x/13*a.y/5*19*654%53>b.z/3*54*b.x/13*b.y/5*19*654%53;
    }
};
struct Comp22
{
    bool operator()(const st& a,const st& b)
    {
        return a.z/3*54*a.x/13*a.y/5*19*654%53<b.z/3*54*b.x/13*b.y/5*19*654%53;
    }
};
struct Comp23
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*a.x-a.y*3<b.z*b.x-b.y*3;
    }
};
struct Comp24
{
    bool operator()(const st& a,const st& b)
    {
        return a.z*a.x-a.y*3>b.z*b.x-b.y*3;
    }
};
st t;
priority_queue <st,vector<st>,Comp> pq;
priority_queue <st,vector<st>,Comp2> pq2;
priority_queue <st,vector<st>,Comp3> pq3;
priority_queue <st,vector<st>,Comp4> pq4;
priority_queue <st,vector<st>,Comp5> pq5;
priority_queue <st,vector<st>,Comp6> pq6;
priority_queue <st,vector<st>,Comp7> pq7;
priority_queue <st,vector<st>,Comp8> pq8;
priority_queue <st,vector<st>,Comp9> pq9;
priority_queue <st,vector<st>,Comp10> pq10;
priority_queue <st,vector<st>,Comp11> pq11;
priority_queue <st,vector<st>,Comp12> pq12;
priority_queue <st,vector<st>,Comp13> pq13;
priority_queue <st,vector<st>,Comp14> pq14;
priority_queue <st,vector<st>,Comp15> pq15;
priority_queue <st,vector<st>,Comp16> pq16;
priority_queue <st,vector<st>,Comp17> pq17;
priority_queue <st,vector<st>,Comp18> pq18;
priority_queue <st,vector<st>,Comp19> pq19;
priority_queue <st,vector<st>,Comp20> pq20;
priority_queue <st,vector<st>,Comp21> pq21;
priority_queue <st,vector<st>,Comp22> pq22;
priority_queue <st,vector<st>,Comp23> pq23;
priority_queue <st,vector<st>,Comp24> pq24;
int n,r,k;
int a[128][128][128],b[128][128][128],ans[128][128][128],ansbr[128];
int bfs(int x,int y,int z,int Q)
{
    int br=0;
    queue <st> q;
    t.x=x;
    t.y=y;
    t.z=z;
    q.push(t);
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        x=t.x;
        y=t.y;
        z=t.z;
        if(x<1||y<1||x>n||y>n)continue;
        if(b[Q][x][y]==-1)continue;
        b[Q][x][y]=-1;
        br++;
        if(br==z)break;
        if(x+1<=n)
        if(b[Q][x+1][y]==0||b[Q][x+1][y]==z)
        {
            t.x=x+1;
            t.y=y;
            q.push(t);
        }

        if(y+1<=n)
        if(b[Q][x][y+1]==0||b[Q][x][y+1]==z)
        {
            t.x=x;
            t.y=y+1;
            q.push(t);
        }

        if(x-1<=n)
        if(b[Q][x-1][y]==0||b[Q][x-1][y]==z)
        {
            t.x=x-1;
            t.y=y;
            q.push(t);
        }

        if(y-1<=n)
        if(b[Q][x][y-1]==0||b[Q][x][y-1]==z)
        {
            t.x=x;
            t.y=y-1;
            q.push(t);
        }
    }
    return br;
}
void bfs2(int x,int y,int z,int Q)
{
    int br=0;
    queue <st> q;
    t.x=x;
    t.y=y;
    t.z=z;
    q.push(t);
    while(!q.empty())
    {


        t=q.front();
        q.pop();
        x=t.x;
        y=t.y;
        z=t.z;
        if(x<1||y<1||x>n||y>n)continue;
        if(a[Q][x][y]==-1)continue;
        a[Q][x][y]=-1;
        ans[Q][x][y]=k;
        br++;
        if(br==z)break;
        if(x+1<=n)
        if(a[Q][x+1][y]==0||a[Q][x+1][y]==z)
        {
            t.x=x+1;
            t.y=y;
            q.push(t);
        }

        if(y+1<=n)
        if(a[Q][x][y+1]==0||a[Q][x][y+1]==z)
        {
            t.x=x;
            t.y=y+1;
            q.push(t);
        }

        if(x-1>=1)
        if(a[Q][x-1][y]==0||a[Q][x-1][y]==z)
        {
            t.x=x-1;
            t.y=y;
            q.push(t);
        }

        if(y-1>=1)
        if(a[Q][x][y-1]==0||a[Q][x][y-1]==z)
        {
            t.x=x;
            t.y=y-1;
            q.push(t);
        }
    }
}

int main()
{
    fin>>n>>r;
    int x,y,z;
    int u;
    for(int i=1;i<=r;i++)
    {
        fin>>t.x>>t.y>>t.z;
       //
        for(int j=0;j<=ASD;j++)
        {
            a[j][t.x][t.y]=t.z;
            b[j][t.x][t.y]=t.z;
        }
        pq.push(t);
        pq2.push(t);
        pq3.push(t);
        pq4.push(t);
        pq4.push(t);
        pq5.push(t);
        pq6.push(t);
        pq7.push(t);
        pq8.push(t);
        pq9.push(t);
        pq10.push(t);
        pq11.push(t);
        pq12.push(t);
        pq13.push(t);
        pq14.push(t);
        pq15.push(t);
        pq16.push(t);
        pq17.push(t);
        pq18.push(t);
        pq19.push(t);
        pq20.push(t);
        pq21.push(t);
        pq22.push(t);
        pq23.push(t);
        pq24.push(t);
    }
    while(!pq.empty())
    {
        t=pq.top();
        pq.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[1][x][y]==0)
        {
            u=bfs(x,y,z,1);
        }
        if(u==t.z)
        {
            ansbr[1]+=u;
            k++;
            bfs2(x,y,z,1);
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[1][i][j]=a[1][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq2.empty())
    {
        t=pq2.top();
        pq2.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[2][x][y]==0)
        {
            u=bfs(x,y,z,2);
        }
        if(u==t.z)
        {
            ansbr[2]+=u;
            k++;
            bfs2(x,y,z,2);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[2][i][j]=a[2][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq3.empty())
    {
        t=pq3.top();
        pq3.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[3][x][y]==0)
        {
            u=bfs(x,y,z,3);
        }
        if(u==t.z)
        {
            ansbr[3]+=u;
            k++;
            bfs2(x,y,z,3);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[3][i][j]=a[3][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq4.empty())
    {
        t=pq4.top();
        pq4.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[4][x][y]==0)
        {
            u=bfs(x,y,z,4);
        }
        if(u==t.z)
        {
            ansbr[4]+=u;
            k++;
            bfs2(x,y,z,4);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[4][i][j]=a[4][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq5.empty())
    {
        t=pq5.top();
        pq5.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[5][x][y]==0)
        {
            u=bfs(x,y,z,5);
        }
        if(u==t.z)
        {
            ansbr[5]+=u;
            k++;
            bfs2(x,y,z,5);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[5][i][j]=a[5][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq6.empty())
    {
        t=pq6.top();
        pq6.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[6][x][y]==0)
        {
            u=bfs(x,y,z,6);
        }
        if(u==t.z)
        {
            ansbr[6]+=u;
            k++;
            bfs2(x,y,z,6);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[6][i][j]=a[6][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq7.empty())
    {
        t=pq7.top();
        pq7.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[7][x][y]==0)
        {
            u=bfs(x,y,z,7);
        }
        if(u==t.z)
        {
            ansbr[7]+=u;
            k++;
            bfs2(x,y,z,7);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[7][i][j]=a[7][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq8.empty())
    {
        t=pq8.top();
        pq8.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[8][x][y]==0)
        {
            u=bfs(x,y,z,8);
        }
        if(u==t.z)
        {
            ansbr[8]+=u;
            k++;
            bfs2(x,y,z,8);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[8][i][j]=a[8][i][j];
                }
            }
        }
    }
     k=0;
    while(!pq9.empty())
    {
        t=pq9.top();
        pq9.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[9][x][y]==0)
        {
            u=bfs(x,y,z,9);
        }
        if(u==t.z)
        {
            ansbr[9]+=u;
            k++;
            bfs2(x,y,z,9);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[9][i][j]=a[9][i][j];
                }
            }
        }
    }
     k=0;
    while(!pq10.empty())
    {
        t=pq10.top();
        pq10.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[10][x][y]==0)
        {
            u=bfs(x,y,z,10);
        }
        if(u==t.z)
        {
            ansbr[10]+=u;
            k++;
            bfs2(x,y,z,10);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[10][i][j]=a[10][i][j];
                }
            }
        }
    }
     k=0;
    while(!pq11.empty())
    {
        t=pq11.top();
        pq11.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[11][x][y]==0)
        {
            u=bfs(x,y,z,11);
        }
        if(u==t.z)
        {
            ansbr[11]+=u;
            k++;
            bfs2(x,y,z,11);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[11][i][j]=a[11][i][j];
                }
            }
        }
    }
     k=0;
    while(!pq12.empty())
    {
        t=pq12.top();
        pq12.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[12][x][y]==0)
        {
            u=bfs(x,y,z,12);
        }
        if(u==t.z)
        {
            ansbr[12]+=u;
            k++;
            bfs2(x,y,z,12);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[12][i][j]=a[12][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq13.empty())
    {
        t=pq13.top();
        pq13.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[13][x][y]==0)
        {
            u=bfs(x,y,z,13);
        }
        if(u==t.z)
        {
            ansbr[13]+=u;
            k++;
            bfs2(x,y,z,13);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[13][i][j]=a[13][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq14.empty())
    {
        t=pq14.top();
        pq14.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[14][x][y]==0)
        {
            u=bfs(x,y,z,14);
        }
        if(u==t.z)
        {
            ansbr[14]+=u;
            k++;
            bfs2(x,y,z,14);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[14][i][j]=a[14][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq15.empty())
    {
        t=pq15.top();
        pq15.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[15][x][y]==0)
        {
            u=bfs(x,y,z,15);
        }
        if(u==t.z)
        {
            ansbr[15]+=u;
            k++;
            bfs2(x,y,z,15);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[15][i][j]=a[15][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq16.empty())
    {
        t=pq16.top();
        pq16.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[16][x][y]==0)
        {
            u=bfs(x,y,z,16);
        }
        if(u==t.z)
        {
            ansbr[16]+=u;
            k++;
            bfs2(x,y,z,16);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[16][i][j]=a[16][i][j];
                }
            }
        }
    }
k=0;
    while(!pq17.empty())
    {
        t=pq17.top();
        pq17.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[17][x][y]==0)
        {
            u=bfs(x,y,z,17);
        }
        if(u==t.z)
        {
            ansbr[17]+=u;
            k++;
            bfs2(x,y,z,17);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[17][i][j]=a[17][i][j];
                }
            }
        }
    }
    k=0;
    while(!pq18.empty())
    {
        t=pq18.top();
        pq18.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[18][x][y]==0)
        {
            u=bfs(x,y,z,18);
        }
        if(u==t.z)
        {
            ansbr[18]+=u;
            k++;
            bfs2(x,y,z,18);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[18][i][j]=a[18][i][j];
                }
            }
        }
    }
k=0;
    while(!pq19.empty())
    {
        t=pq19.top();
        pq19.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[19][x][y]==0)
        {
            u=bfs(x,y,z,19);
        }
        if(u==t.z)
        {
            ansbr[19]+=u;
            k++;
            bfs2(x,y,z,19);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[19][i][j]=a[19][i][j];
                }
            }
        }
    }
k=0;
    while(!pq20.empty())
    {
        t=pq20.top();
        pq20.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[20][x][y]==0)
        {
            u=bfs(x,y,z,20);
        }
        if(u==t.z)
        {
            ansbr[20]+=u;
            k++;
            bfs2(x,y,z,20);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[20][i][j]=a[20][i][j];
                }
            }
        }
    }
k=0;
    while(!pq21.empty())
    {
        t=pq21.top();
        pq21.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[21][x][y]==0)
        {
            u=bfs(x,y,z,21);
        }
        if(u==t.z)
        {
            ansbr[21]+=u;
            k++;
            bfs2(x,y,z,21);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[21][i][j]=a[21][i][j];
                }
            }
        }
    }
k=0;
    while(!pq22.empty())
    {
        t=pq22.top();
        pq22.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[22][x][y]==0)
        {
            u=bfs(x,y,z,22);
        }
        if(u==t.z)
        {
            ansbr[22]+=u;
            k++;
            bfs2(x,y,z,22);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[22][i][j]=a[22][i][j];
                }
            }
        }
    }
k=0;
    while(!pq23.empty())
    {
        t=pq23.top();
        pq23.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[23][x][y]==0)
        {
            u=bfs(x,y,z,23);
        }
        if(u==t.z)
        {
            ansbr[23]+=u;
            k++;
            bfs2(x,y,z,23);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[23][i][j]=a[23][i][j];
                }
            }
        }
    }

k=0;
    while(!pq24.empty())
    {
        t=pq24.top();
        pq24.pop();
        u=0;
        x=t.x;
        y=t.y;
        z=t.z;
        if(ans[24][x][y]==0)
        {
            u=bfs(x,y,z,24);
        }
        if(u==t.z)
        {
            ansbr[24]+=u;
            k++;
            bfs2(x,y,z,24);
        }
        else
        {//fout<<1<<endl;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    b[24][i][j]=a[24][i][j];
                }
            }
        }
    }




    k=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[0][i][j]>0)
            {
                u=bfs(i,j,a[0][i][j],0);
                if(u==a[0][i][j])
                {
                    ansbr[0]+=u;
                    k++;
                    bfs2(i,j,a[0][i][j],0);
                }
                else
                {//fout<<1<<endl;
                    for(int i=1;i<=n;i++)
                    {
                        for(int j=1;j<=n;j++)
                        {
                            b[0][i][j]=a[0][i][j];
                        }
                    }
                }

            }
        }
    }


    int e=0;
    for(int i=0;i<=ASD;i++)
    {
        if(ansbr[i]>ansbr[e])e=i;
       // cout<<ansbr[i]<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        fout<<ans[e][i][1];
        for(int j=2;j<=n;j++)
        {
            fout<<" "<<ans[e][i][j];
        }
        fout<<endl;
    }
    return 0;
}
/*

tl : 5 sec
mem lim : 256

*