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

using namespace std;

typedef long long ll;

const int N = 601;
const ll INF = 1e18 + 239;

ll d[N][N];
int e[N][N];

int used[N];
ll ans[N];

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

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            e[i][j] = -1;
        }
    }
    while (m--) {
        int u, v, c;
        cin >> u >> v >> c;
        e[u][v] = c;
    }
    for (int st = 0; st < n; st++) {
        fill(d[st], d[st] + n, INF);
        fill(used, used + n, 0);
        d[st][st] = 0;
        for (int it = 0; it < n; it++) {
            int v = -1;
            for (int cand = 0; cand < n; cand++) {
                if (used[cand]) continue;
                if (v == -1 || d[st][v] > d[st][cand]) {
                    v = cand;
                }
            }
            used[v] = 1;
            assert(v != -1);
            for (int to = 0; to < n; to++) {
                if (e[v][to] == -1) continue;
                int nx = (to + d[st][v]) % n;
                ll tot = d[st][v] + e[v][to];
                d[st][nx] = min(d[st][nx], tot);
                int add = ((st + 1) % n - nx + n) % n;
                nx = (nx + add) % n;
                tot += add;
                d[st][nx] = min(d[st][nx], tot);
            }
            if (st != v) {
                int nx = (v + 1) % n;
                d[st][nx] = min(d[st][nx], d[st][v] + 1);
            }
            // if (st == v && e[v][v] != -1) {
            //     int nx = (v + 1) % n;
            //     d[st][nx] = min(d[st][nx], d[st][v] + e[v][v] + 1);
            // }
        }
    }
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            cout << d[u][v] << ' ';
        }
        cout << '\n';
    }
}