#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int MAXN=111;
struct flag
{
    int x,y,c;
    int nopass;
};
int n,r,k;
int seen;
int used[MAXN][MAXN],flags[MAXN][MAXN],mark[MAXN][MAXN];
int used1[MAXN][MAXN],mark1[MAXN][MAXN];
int remote[MAXN][MAXN];
int lowpr[MAXN][MAXN];
vector<int> v;
vector<flag> toadd;
flag a[MAXN*16];
queue<flag> q;
void read()
{
    int i;
    scanf("%d",&n);
    scanf("%d",&r);
    for(i=1;i<=r;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
        flags[a[i].x][a[i].y]=a[i].c;
        lowpr[a[i].x-1][a[i].y]=a[i].c;
        lowpr[a[i].x+1][a[i].y]=a[i].c;
        lowpr[a[i].x][a[i].y-1]=a[i].c;
        lowpr[a[i].x][a[i].y+1]=a[i].c;
    }
    for(i=0;i<=n+1;i++)
        mark[0][i]=mark[n+1][i]=mark[i][0]=mark[i][n+1]=-1;
    for(i=0;i<=n+1;i++)
        mark1[0][i]=mark1[n+1][i]=mark1[i][0]=mark1[i][n+1]=-1;
}
bool cmp(flag el1,flag el2)
{
    return el1.c*20-el1.nopass>el2.c*20-el2.nopass;
    return el1.c>el2.c;
}
void expandArea(int curr)
{
    //printf("%d %d %d %d\n",a[curr].x,a[curr].y,a[curr].c,a[curr].nopass);
    if(used[a[curr].x][a[curr].y]!=0)return;
    int i,j,l,cnt=0;
    flag el,el1;
    q.push(a[curr]);
    k++;
    mark[a[curr].x][a[curr].y]=k;
    while(!q.empty())
    {
        el=q.front();
        q.pop();
        cnt++;
        //if(k==2)printf("!%d %d\n",el.x,el.y);
        mark[el.x][el.y]+=MAXN*MAXN;
        if(cnt==a[curr].c)break;
        l=0;
        /// check for free
        el1.x=el.x+1;
        el1.y=el.y;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&lowpr[el1.x][el1.y]==0)
        {
            l++;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        el1.x=el.x;
        el1.y=el.y+1;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&lowpr[el1.x][el1.y]==0)
        {
            l++;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        el1.x=el.x-1;
        el1.y=el.y;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&lowpr[el1.x][el1.y]==0)
        {
            l++;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        el1.x=el.x;
        el1.y=el.y-1;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&lowpr[el1.x][el1.y]==0)
        {
            l++;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        /// check for free and equal
        if(l<2)
        {
            el1.x=el.x+1;
            el1.y=el.y;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&(lowpr[el1.x][el1.y]==0||lowpr[el1.x][el1.y]==a[curr].c))
            {
                l++;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
            el1.x=el.x;
            el1.y=el.y+1;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&(lowpr[el1.x][el1.y]==0||lowpr[el1.x][el1.y]==a[curr].c))
            {
                l++;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
            el1.x=el.x-1;
            el1.y=el.y;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&(lowpr[el1.x][el1.y]==0||lowpr[el1.x][el1.y]==a[curr].c))
            {
                l++;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
            el1.x=el.x;
            el1.y=el.y-1;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c)&&(lowpr[el1.x][el1.y]==0||lowpr[el1.x][el1.y]==a[curr].c))
            {
                l++;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
        }
        /// check for any cell
        if(l<2)
        {
            el1.x=el.x+1;
            el1.y=el.y;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
            {
                l=1;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
            el1.x=el.x-1;
            el1.y=el.y;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
            {
                l=1;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
            el1.x=el.x;
            el1.y=el.y+1;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
            {
                l=1;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
            el1.x=el.x;
            el1.y=el.y-1;
            if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
            {
                l=1;
                q.push(el1);
                mark[el1.x][el1.y]=k;
            }
        }
    }
    if(cnt!=a[curr].c)k--;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            l=0;
            if(mark[i][j]>MAXN*MAXN)
            {
                l=1;
                mark[i][j]-=MAXN*MAXN;
            }
            if(cnt==a[curr].c&&l==1)used[i][j]=mark[i][j];
            else mark[i][j]=used[i][j];
        }
    while(!q.empty())q.pop();
    //if(cnt==a[curr].c)printf("%d %d\n",k,a[curr].c);
}
void computePassable(int curr)
{
    if(used[a[curr].x][a[curr].y]!=0)return;
    int i,j,l=0,cnt=0;
    flag el,el1;
    q.push(a[curr]);
    mark[a[curr].x][a[curr].y]=k;
    while(!q.empty())
    {
        el=q.front();
        q.pop();
        cnt++;
        //if(k==2)printf("!%d %d\n",el.x,el.y);
        mark[el.x][el.y]+=MAXN*MAXN;
        if(cnt==a[curr].c)break;
        el1.x=el.x+1;
        el1.y=el.y;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
        {
            l=1;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        else
        if(flags[el1.x][el1.y]!=0&&flags[el1.x][el1.y]!=a[curr].c)l++;
        el1.x=el.x-1;
        el1.y=el.y;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
        {
            l=1;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        else
        if(flags[el1.x][el1.y]!=0&&flags[el1.x][el1.y]!=a[curr].c)l++;
        el1.x=el.x;
        el1.y=el.y+1;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
        {
            l=1;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        else
        if(flags[el1.x][el1.y]!=0&&flags[el1.x][el1.y]!=a[curr].c)l++;
        el1.x=el.x;
        el1.y=el.y-1;
        if(mark[el1.x][el1.y]==0&&(flags[el1.x][el1.y]==0||flags[el1.x][el1.y]==a[curr].c))
        {
            l=1;
            q.push(el1);
            mark[el1.x][el1.y]=k;
        }
        else
        if(flags[el1.x][el1.y]!=0&&flags[el1.x][el1.y]!=a[curr].c)l++;
    }
    a[curr].nopass=l;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            mark[i][j]=used[i][j];
    while(!q.empty())q.pop();
}
void findDistance(int curr)
{
    int i,sz;
    for(i=1;i<=r;i++)
        if(a[i].c!=a[curr].c)
            v.push_back(abs(a[curr].x-a[i].x)+abs(a[curr].y-a[i].y));
    sort(v.begin(),v.end());
    sz=v.size();
    for(i=min(sz-1,1);i<min(sz,4);i++)
        a[curr].nopass+=v[i];
    v.clear();
}
void init()
{
    int i;
    for(i=1;i<=n;i++)
        findDistance(i);
        //computePassable(i);
}
void solve()
{
    int i;
    sort(a+1,a+(r+1),cmp);
    for(i=1;i<=r;i++){
        expandArea(i);}
}
void findRemoteness()
{
    int i,j,h,sz;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            for(h=1;h<=r;h++)
                v.push_back(abs(i-a[h].x)+abs(j-a[h].y));
            sort(v.begin(),v.end());
            sz=v.size();
            for(h=min(sz-1,1);h<min(sz,4);h++)
                remote[i][j]+=v[h];
            v.clear();
        }
}
bool cmp1(flag el1,flag el2)
{
    return el1.c>el2.c;
}
void dfs(int curr,int x,int y)
{
    //if(k==2)printf("%d %d %d %d\n",x,y,seen,a[curr].c);
    if(seen==a[curr].c)return;
    mark1[x][y]=k;
    seen++;
    flag el;
    flag next;
    el.x=x+1;
    el.y=y;
    if(mark1[el.x][el.y]==0&&(flags[el.x][el.y]==0||flags[el.x][el.y]==a[curr].c))
    {
        next.x=el.x;
        next.y=el.y;
        next.c=remote[el.x][el.y];
        toadd.push_back(next);
    }
    el.x=x;
    el.y=y+1;
    if(mark1[el.x][el.y]==0&&(flags[el.x][el.y]==0||flags[el.x][el.y]==a[curr].c))
    {
        next.x=el.x;
        next.y=el.y;
        next.c=remote[el.x][el.y];
        toadd.push_back(next);
    }
    el.x=x-1;
    el.y=y;
    if(mark1[el.x][el.y]==0&&(flags[el.x][el.y]==0||flags[el.x][el.y]==a[curr].c))
    {
        next.x=el.x;
        next.y=el.y;
        next.c=remote[el.x][el.y];
        toadd.push_back(next);
    }
    el.x=x;
    el.y=y-1;
    if(mark1[el.x][el.y]==0&&(flags[el.x][el.y]==0||flags[el.x][el.y]==a[curr].c))
    {
        next.x=el.x;
        next.y=el.y;
        next.c=remote[el.x][el.y];
        toadd.push_back(next);
    }
    sort(toadd.begin(),toadd.end(),cmp1);
    for(int i=0;i<toadd.size();i++)
        if(mark1[toadd[i].x][toadd[i].y]==0)dfs(curr,toadd[i].x,toadd[i].y);
    toadd.clear();
}
void solve1()
{
    int i,j,h;
    k=0;
    sort(a+1,a+(r+1),cmp);
    for(h=1;h<=r;h++)
    {
        if(used[a[h].x][a[h].y]!=0)continue;
        seen=0;
        k++;
        dfs(h,a[h].x,a[h].y);
        if(seen!=a[h].c)k--;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(seen==a[h].c)used1[i][j]=mark1[i][j];
                else mark1[i][j]=used1[i][j];
            }
        //if(k==2)break;
    }
}
void compareAnswers()
{
    int i,j,answer1=0,answer2=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(used[i][j]>0)answer1++;
            if(used1[i][j]>0)answer2++;
        }
    if(answer2>answer1)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                used[i][j]=used1[i][j];
    }
}
void print()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<n;j++)
            printf("%d ",used[i][j]);
        printf("%d\n",used[i][j]);
    }
}
int main()
{
    freopen("regions.in","r",stdin);
    freopen("regions.out","w",stdout);
    read();
    init();
    solve();
    findRemoteness();
    solve1();
    compareAnswers();
    print();
}
/*
5 14
1 1 3
1 4 6
1 5 6
2 1 5
2 3 4
2 5 6
3 2 5
4 2 1
3 3 4
3 5 6
4 4 6
5 3 3
5 4 1
5 5 2
*