#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define X first
#define Y second
#define pb push_back
#define sz(s) int64_t(s.size())
#define make_unique(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())

const ll mod = 998244353;

template<class T>
istream& operator >> (istream& in, vector<T>& v){ for (auto &x : v) { in >> x; } return in; }

template<class T, class U>
istream& operator >> (istream& in, pair<T, U> & v){ in >> v.X >> v.Y;return in; }

template<class T, class U>
ostream& operator << (ostream& out, pair<T, U> & v){ out << v.X << " " << v.Y;return out; }


template<class T, class U>
void chkmax(T &a, U b) {
    a = max(a, (T)b);
    return;
}

template<class T, class U>
void chkmin(T &a, U b) {
    a = min(a, (T)b);
    return;
}

ll ppow (ll x, ll s) {
    ll res = 1;
    while (s) {
        if (s%2) {
            (res *= x) %= mod;
        }
        (x *= x) %= mod;
        s /= 2;
    }
    return res;
}

vector<int> zf (string s) {

    int n = sz(s);

    vector<int> z (n);

    for (int i = 1, l = 0, r = 0; i < n; i++) {

        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);

        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;

        if (i + z[i] - 1 > r)
            l = i,  r = i + z[i] - 1;

    }

    return z;

}

vector<int> pf(string p) {
    int n = sz(p);
    vector<int> pref_fun(n, 0);

    for (int i = 1;i < n;i++) {
        int j = pref_fun[i - 1];
        while (j > 0 && p[i] != p[j])
            j = pref_fun[j - 1];
        if (p[i] == p[j])
            j++;
        pref_fun[i] = j;
    }
    return pref_fun;
}

vector<vector<int> > mul(vector<vector<int> > &a, vector<vector<int> > &b) {
    int n = sz(a);
    vector<vector<int> > c(n, vector<int> (n, 0));

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            for (int k = 0;k < n;k++) {
                ll ga = a[i][k];
                ga *= b[k][j];
                ga %= mod;
                c[i][j] += ga;
                if (c[i][j] >= mod) {
                    c[i][j] -= mod;
                }
            }
        }
    }

    return c;
}

vector<vector<int> > matrix_pow(vector<vector<int> > a, ll y) {
    int n = sz(a);
    vector<vector<int> > res(n, vector<int> (n, 0));
    for (int i = 0;i < n;i++) res[i][i] = 1;
    while (y) {
        if (y%2 == 1) {
            res = mul(res, a);
            y--;
        }else {
            a = mul(a, a);
            y /= 2;
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    const int inf = 1e9 + 10000;
    vector<vector<int> > gr(n, vector<int> (n, inf));
    vector<vector<ll> > d(n, vector<ll> (n, (ll)inf * inf));

    vector<vector<pair<int,int> > > grr(n);

    for (int i = 0;i < m;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        chkmin(gr[a][b], c);
        grr[a].pb({b, c});
    }

    for (int i = 0;i < n;i++) {
        vector<int> used(n, false);
        for (auto [x, w] : grr[i]) {
            chkmin(d[i][x], w);
        }
        while (true) {
            int ind = -1;
            for (int j = 0;j < n;j++) {
                if (!used[j] && d[i][j] < inf) {
                    if (ind == -1 || d[i][j] < d[i][ind]) ind = j;
                }
            }
            if (ind == -1) break;
            used[ind] = 1;
            for (int j = 0;j < n;j++) {
                chkmin(d[i][(j + d[i][ind])%n], d[i][ind] + gr[ind][j]);
            }
            chkmin(d[i][(ind + 1)%n], d[i][ind] + 1);
        }
        d[i][i] = 0;
        for (auto x : d[i]) cout << x << " ";
        cout << '\n';
    }


    return 0;
}