/// TL = 5s
/// ML = 256 MB
# include <cstdio>
# include <cmath>
# include <ctime>
# include <cstdlib>
# include <cstring>
# include <string>
# include <vector>
# include <queue>
# include <map>
# include <algorithm>
# include <iostream>

using namespace std;

const int MAX_N = 128;
const double TL = 4.6;

struct flag
{
        int x;
        int y;
        int c;
        int p;
        int nu;
};

int n;
int r;

int a[MAX_N][MAX_N];
int used[MAX_N][MAX_N];

flag fl[16 * MAX_N];

int curr;
int curr_k;
int curr_t[MAX_N][MAX_N];

int ans;
int ans_k;
int ans_t[MAX_N][MAX_N];

int aa[4] = {-1, 1, 0, 0};
int bb[4] = {0, 0, -1, 1};

inline int m_abs (int pp)
{
        return (pp < 0) ? -pp : pp;
}

bool cmp_Sm (flag p, flag q)
{
        return p.c < q.c;
}

bool cmp_Bg (flag p, flag q)
{
        return q.c < p.c;
}

bool Sm_P (flag p, flag q)
{
        return p.p < q.p;
}

bool Bg_P (flag p, flag q)
{
        return q.p < p.p;
}

bool near_end (flag p, flag q)
{
        return min (q.x - 1, n - q.x) + min (q.y - 1, n - q.y) > min (p.x - 1, n - p.x) + min (p.y - 1, n - p.y);
}



bool Time ()
{
        return (double (double (clock ()) / double (CLOCKS_PER_SEC)) < TL);
}

void Print_Current ()
{
        int i, j;
        printf ("%d\n", curr);
        printf ("%d\n", curr_k);
        for (i = 1; i <= n; i ++)
        {
                for (j = 1; j <= n; j ++)
                        printf ("%d ", curr_t[i][j]);
                printf ("\n");
        }
}

void Print (int op)
{
        int i, j;
        if (!op)
        {
                printf ("%d\n", ans);
                printf ("%d\n", ans_k);
        }
        for (i = 1; i <= n; i ++)
        {
                for (j = 1; j <= n; j ++)
                        printf ("%d ", ans_t[i][j]);
                printf ("\n");
        }
}


void Check ()
{
        if (ans < curr)
        {
                int i, j;
                ans = curr;
                ans_k = curr_k;
                for (i = 1; i <= n; i ++)
                        for (j = 1; j <= n; j ++)
                                ans_t[i][j] = curr_t[i][j];
        }
}

void Read ()
{
        ///freopen ("input.txt", "r", stdin);
        freopen ("regions.in", "r", stdin);
        freopen ("regions.out", "w", stdout);

        int i, j;
        scanf ("%d%d", &n, &r);

        for (i = 1; i <= r; i ++)
        {
                scanf ("%d%d%d", &fl[i].x, &fl[i].y, &fl[i].c);
                fl[i].nu = i;
                a[fl[i].x][fl[i].y] = fl[i].c;
        }

}

bool bfs (int x, int op)
{
        ///printf ("%d %d %d\n", fl[x].nu, fl[x].c, op);
        ///cerr << fl[x].nu << " " << fl[x].c << " " <<  fl[x].x << " " << fl[x].y << " " << op << " " << x << endl;

        int i, j, st = x, cnt = 0, cx, cy, nx, ny;
        queue <pair <int, int> > q;
        pair <int, int> t, nt;

        memset (used, 0, sizeof (used));

        while (!q.empty ())
                q.pop ();
        q.push (make_pair (fl[st].x, fl[st].y));

        used[fl[st].x][fl[st].y] = 1;

        while (!q.empty ())
        {
                t = q.front ();
                q.pop ();
                cnt ++;
                cx = t.first;
                cy = t.second;
                ///used[cx][cy] = 1;
                if (op)
                        curr_t[cx][cy] = curr_k;

                if (cnt >= fl[st].c)
                        return true;

                for (i = 0; i < 4; i ++)
                {
                        nx = cx + aa[i];
                        ny = cy + bb[i];
                        if (nx < 1 || n < nx)
                                continue;

                        if (ny < 1 || n < ny)
                                continue;

                        if (curr_t[nx][ny] != 0)
                                continue;

                        if (a[nx][ny] > 0)
                                if (a[nx][ny] != fl[st].c)
                                        continue;

                        if (used[nx][ny])
                                continue;

                        nt.first = nx;
                        nt.second = ny;
                        used[nx][ny] = 1;
                        q.push (nt);
                }

        }
        return false;
}

void Greedy1 ()
{
        int i;
        curr = 0;
        curr_k = 0;
        memset  (curr_t, 0, sizeof (curr_t));

        sort (fl + 1, fl + r + 1, cmp_Sm);
        for (i = 1; i <= r; i ++)
        {
                if (curr_t[fl[i].x][fl[i].y])
                        continue;
                if (bfs (i, 0))
                {
                        curr_k ++;
                        curr = curr + fl[i].c;
                        bfs (i, 1);
                        ///Print_Current ();
                }
        }
        ///printf ("///////////////////////////\n");
        ///Print_Current ();

        Check ();
}

void Greedy2 ()
{
        int i;
        curr = 0;
        curr_k = 0;
        memset  (curr_t, 0, sizeof (curr_t));

        sort (fl + 1, fl + r + 1, cmp_Bg);
        for (i = 1; i <= r; i ++)
        {
                if (curr_t[fl[i].x][fl[i].y])
                        continue;
                if (bfs (i, 0))
                {
                        curr_k ++;
                        curr = curr + fl[i].c;
                        bfs (i, 1);
                        ///Print_Current ();
                }
        }
        ///printf ("///////////////////////////\n");
        ///Print_Current ();

        Check ();
}


void Greedy3 ()
{
        int i, l, rr, t;
        curr = 0;
        curr_k = 0;
        memset  (curr_t, 0, sizeof (curr_t));

        sort (fl + 1, fl + r + 1, cmp_Sm);
        l = 1;
        rr = r;
        for (i = 1; i <= r; i ++)
        {
                if (i & 1)
                        t = l;
                else
                        t = rr;
                if (curr_t[fl[t].x][fl[t].y])
                        continue;
                if (bfs (t, 0))
                {
                        curr_k ++;
                        curr = curr + fl[t].c;
                        bfs (t, 1);
                        ///Print_Current ();
                }
                if (i & 1)
                        l ++;
                else
                        rr --;
        }
        ///printf ("///////////////////////////\n");
        ///Print_Current ();

        Check ();
}

void Greedy4 ()
{
        int i;
        curr = 0;
        curr_k = 0;
        memset  (curr_t, 0, sizeof (curr_t));

        sort (fl + 1, fl + r + 1, near_end);
        for (i = 1; i <= r; i ++)
        {
                if (curr_t[fl[i].x][fl[i].y])
                        continue;
                if (bfs (i, 0))
                {
                        curr_k ++;
                        curr = curr + fl[i].c;
                        bfs (i, 1);
                        ///Print_Current ();
                }
        }
        ///printf ("///////////////////////////\n");
        ///Print_Current ();

        Check ();
}

void Greedy5 ()
{
        int i;
        curr = 0;
        curr_k = 0;
        memset  (curr_t, 0, sizeof (curr_t));

        sort (fl + 1, fl + r + 1, Sm_P);
        for (i = 1; i <= r; i ++)
        {
                if (curr_t[fl[i].x][fl[i].y])
                        continue;
                if (bfs (i, 0))
                {
                        curr_k ++;
                        curr = curr + fl[i].c;
                        bfs (i, 1);
                        ///Print_Current ();
                }
        }
        ///printf ("///////////////////////////\n");
        ///Print_Current ();

        Check ();
}

void Greedy6 ()
{
        int i;
        curr = 0;
        curr_k = 0;
        memset  (curr_t, 0, sizeof (curr_t));

        sort (fl + 1, fl + r + 1, Bg_P);
        for (i = 1; i <= r; i ++)
        {
                if (curr_t[fl[i].x][fl[i].y])
                        continue;
                if (bfs (i, 0))
                {
                        curr_k ++;
                        curr = curr + fl[i].c;
                        bfs (i, 1);
                        ///Print_Current ();
                }
        }
        ///printf ("///////////////////////////\n");
        ///Print_Current ();

        Check ();
}

void Random ()
{
        int i;
        curr = 0;
        curr_k = 0;
        memset  (curr_t, 0, sizeof (curr_t));

        random_shuffle (fl + 1, fl + r + 1);
        for (i = 1; i <= r; i ++)
        {
                if (curr_t[fl[i].x][fl[i].y])
                        continue;
                if (bfs (i, 0))
                {
                        curr_k ++;
                        curr = curr + fl[i].c;
                        bfs (i, 1);
                        ///Print_Current ();
                }
        }
        ///printf ("///////////////////////////\n");
        ///Print_Current ();

        Check ();
}

void Calc_P ()
{
        int i, j;
        for (i = 1; i <= r; i ++)
                fl[i].p = 0;
        for (i = 1; i <= r; i ++)
                for (j = 1; j <= r; j ++)
                        fl[i].p = fl[i].p + m_abs (fl[i].x - fl[j].x) + m_abs (fl[i].y - fl[j].y);
}

void Calc_P_Centre ()
{
        int i, j, min1, min2;
        min2 = n / 2 + 1;
        if (!(n & 1))
                min1 = n / 2;
        else
                min1 = min2;

        for (i = 1; i <= r; i ++)
        {
                fl[i].p = 0;
                if (fl[i].x <= min1)
                        fl[i].p = fl[i].p + min1 - fl[i].x;
                else
                        fl[i].p = fl[i].p + fl[i].x - min2;

                if (fl[i].y <= min1)
                        fl[i].p = fl[i].p + min1 - fl[i].y;
                else
                        fl[i].p = fl[i].p + fl[i].y - min2;
        }
}

int main ()
{
        Read ();

        Greedy1 ();
        Greedy2 ();
        Greedy3 ();
        Greedy4 ();

        Calc_P ();
        Greedy5 ();
        Greedy6 ();

        Calc_P_Centre ();
        Greedy5 ();
        Greedy6 ();

        while (Time ())
                Random ();

        Print (1);

        return 0;
}