#include <bits/stdc++.h>
using namespace std;

const int maxn = 610;
const int inf = 0x3f3f3f3f;

int n, m;
vector<pair<int, int> > g[maxn];

bool vis[maxn];
int dis[maxn], temp[maxn];
void dij (int s)
{
    fill_n (dis, n + 1, inf);
    fill_n (vis, n + 1, 0);
    dis[s] = 0; int cnt = 1;
    while (cnt <= n)
    {
        int u = 0, d = inf;
        for (int i = 1; i <= n; i++) if (!vis[i] && dis[i] < d) {u = i; d = dis[i];}
        fill_n (temp, n + 1, inf);
        vis[u] = 1;

        for (auto [w, _v] : g[u])
        {
            int v = (_v + dis[u] - 1) % n + 1;
            temp[v] = min (temp[v], dis[u] + w);
        }
        for (int i = 2; i <= n; i++) temp[i] = min (temp[i], temp[i - 1] + 1);
        temp[1] = min (temp[1], temp[n] + 1);
        for (int i = 2; i <= n; i++) temp[i] = min (temp[i], temp[i - 1] + 1);
        for (int i = 1; i <= n; i++) dis[i] = min (dis[i], temp[i]);
        cnt++;
    }
    for (int i = 1; i <= n; i++) printf ("%d ", dis[i]);
}

int main()
{
    scanf ("%d %d", &n, &m);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        scanf ("%d %d %d", &u, &v, &w); u++, v++;
        g[u].push_back({w, v});
    }
    for (int i = 1; i <= n; i++, puts ("")) dij (i);
    return 0;
}
