#include <bits/stdc++.h>

#define ll long long
#define db double
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<db, db>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvvvi vector<vvvi>
#define vll vector<ll>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vvvvll vector<vvvll>
#define vs vector<str>
#define vvs vector<vs>
#define vdb vector<db>
#define vvdb vector<vdb>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vpdd vector<pdd>
#define vvpdd vector<vpdd>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)

#define edg pair<ll, pair<pii, int>>
#define U se.fi.fi
#define V se.fi.se
#define W fi
#define I se.se
#define vedg vector<edg>


using namespace std;
ll INF = LONG_LONG_MAX / 2;
int inf = INT_MAX / 2;
ll mod = 1000000000 + 7;

template <typename T, typename L>
void read(vector<T> & _data, L _size, int _shift) {
    _data.resize(_size + _shift);
    for (ll i = _shift; i < _size + _shift; i++)
        cin >> _data[i];
}

template <typename T, typename L>
void read(vector<vector<T>> & _data, L _rows, L _cols, int _shiftRows, int _shiftCols) {
    _data.resize(_rows + _shiftRows);
    for (ll i = 0; i < _rows + _shiftRows; i++)
        _data[i].resize(_cols + _shiftCols);
    for (ll i = _shiftRows; i < _rows + _shiftRows; i++)
        for (ll j = _shiftCols; j < _cols + _shiftCols; j++)
            cin >> _data[i][j];
}

template <typename T>
void write(vector<T> & _data, ll _shift) {
    for (ll i = _shift; i < _data.size(); i++)
        cout << _data[i] << " ";
    cout << endl;
}


//TODO: SOLUTION
ll n, m;
ll gr[600][600];
ll dists[600][600];
bool been[600];

void clear() {
    rep(i, 0, 600) {
        rep(j, 0, 600) {
            gr[i][j] = 0;
            dists[i][j] = INF / 2;
        }
    }
}

void clearbeen() {
    rep(i, 0, 600) {
        been[i] = false;
    }
}

void dijkstra(ll src) {

    rep(i, 0, n) {
        if (gr[src][i] != 0) {
            dists[src][i] = gr[src][i];
        }
    }

    for (int q = 0; q < n; q++) {

        ll mind = INF;
        ll x = 0;

        rep(i, 0, n) {
            if (!been[i] && dists[src][i] < mind) {
                mind = dists[src][i];
                x = i;
            }
        }

        been[x] = true;
        for (int y = 0; y < n; y++) {
            if (gr[x][y] != 0) {
                if (been[(y + dists[src][x]) % n])
                    continue;
                dists[src][(y + dists[src][x]) % n] = min(dists[src][(y + dists[src][x]) % n], dists[src][x] + gr[x][y]);
            }
        }

        dists[src][(x + 1) % n] = min(dists[src][(x + 1) % n], dists[src][x] + 1);
    }
}


void solve() {
    cin >> n >> m;

    clear();

    rep(i, 0, m) {
        ll a, b, c; cin >> a >> b >> c;
        gr[a][b] = c;
    }

    rep(i, 0, n) {
        clearbeen();
        dijkstra(i);
    }
    rep(i, 0, n) {
        rep(j, 0, n) {
            if (i == j)
                cout << "0 ";
            else
                cout << dists[i][j] << " ";
        }
        cout << endl;
    }
}


int main() {

    ios::sync_with_stdio(false);
    // TODO: Set value of this variable manually
    bool _multipleTestCases = false;

    if (_multipleTestCases) {
        ll t; cin >> t;
        while (t--)
            solve();
    }
    else {
        solve();
    }

    return 0;
}