// Author: Tsukimaru Oshawott
// In the name of
//
//      _/_/      _/_/_/        _/_/_/    _/_/_/_/    _/    _/    _/_/_/_/
//    _/    _/    _/    _/    _/          _/          _/    _/    _/
//    _/_/_/_/    _/_/_/_/    _/          _/_/_/_/    _/    _/    _/_/_/_/
//    _/    _/    _/  _/      _/          _/          _/    _/          _/
//    _/    _/    _/    _/      _/_/_/    _/_/_/_/    _/_/_/_/    _/_/_/_/
//

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define For(i, l, r) for (i = int64(l); i <= int64(r); i++)
#define Fo(i, n) For(i, 1, n)
#define Rof(i, r, l) for (i = int64(r); i >= int64(l); i--)
#define Ro(i, n) Rof(i, n, 1)
#define clr(a) memset(a, 0, sizeof(a))
#define cpy(a, b) memcpy(a, b, sizeof(b))
#define fc(a, ch) memset(a, ch, sizeof(a))

typedef unsigned uint;
typedef unsigned long long uint64;
typedef long long int64;

#define T1 template <class A>
#define T2 template <class A, class B>
#define T3 template <class A, class B, class C>
#define T4 template <class A, class B, class C, class D>
inline void read(char &x) {
    do
        x = getchar();

    while (x <= ' ');
}
inline void read(char *s) {
    char ch;

    do
        ch = getchar();

    while (ch <= ' ');

    while (ch > ' ') {
        (*s) = ch;
        s++;
        ch = getchar();
    }

    (*s) = 0;
}
inline void read(std::string &s) {
    char ch;

    do
        ch = getchar();

    while (ch <= ' ');

    while (ch > ' ') {
        s.push_back(ch);
        ch = getchar();
    }
}
T1 inline void readint(A &x) {
    bool neg = false;
    char ch;

    do
        ch = getchar();

    while (ch <= ' ');

    if (ch == '-') {
        neg = true;
        ch = getchar();
    }

    x = 0;

    while (ch > ' ') {
        x = x * 10 + (ch & 15);
        ch = getchar();
    }

    if (neg)
        x = -x;
}
inline void read(int &x) { readint(x); }
inline void read(uint &x) { readint(x); }
inline void read(int64 &x) { readint(x); }
inline void read(uint64 &x) { readint(x); }

T2 inline void read(A &a, B &b) {
    read(a);
    read(b);
}
T3 inline void read(A &a, B &b, C &c) {
    read(a);
    read(b);
    read(c);
}
T4 inline void read(A &a, B &b, C &c, D &d) {
    read(a);
    read(b);
    read(c);
    read(d);
}
inline void writeln() { putchar('\n'); }
T1 inline void writeint(A x) {
    static char buf[20];
    int top = 0;

    if (!x) {
        putchar('0');
        return;
    }

    if (x < 0) {
        putchar('-');
        x = -x;
    }

    while (x) {
        buf[++top] = (x % 10) | 48;
        x /= 10;
    }

    while (top)
        putchar(buf[top--]);
}
inline void write(int x) { writeint(x); }
inline void write(uint x) { writeint(x); }
inline void write(int64 x) { writeint(x); }
inline void write(uint64 x) { writeint(x); }
inline void write(char ch) { putchar(ch); }
inline void write(char *s) {
    while (*s) {
        putchar(*s);
        s++;
    }
}
inline void write(const char *s) { printf(s); }
T1 inline void write_(A x) {
    write(x);
    putchar(' ');
}
T1 inline void writeln(A x) {
    write(x);
    putchar('\n');
}
T2 inline void write(A a, B b) {
    write_(a);
    write(b);
}
T2 inline void writeln(A a, B b) {
    write_(a);
    writeln(b);
}
T3 inline void writeln(A a, B b, C c) {
    write_(a);
    write_(b);
    writeln(c);
}
T4 inline void writeln(A a, B b, C c, D d) {
    write_(a);
    write_(b);
    write_(c);
    writeln(d);
}
#undef T1
#undef T2
#undef T3
#undef T4

const int N = 600 + 10;

int n, m;
int w[N][N];
int64 dis[N];
bool vis[N];

inline void chkmin(int &a, int b) { a = a < b ? a : b; }
inline void chkmin(int64 &a, int64 b) { a = a < b ? a : b; }

void dijkstra(int s) {
    int i, u, v, p;

    fc(dis, 0x3f);
    clr(vis);
    Fo(v, n) if(w[s][v]) dis[v] = w[s][v];
    Fo(i, n - 1) {
        p = 0;
        Fo(u, n) if (!vis[u] and dis[u] < dis[p]) p = u;
        chkmin(dis[p % n + 1], dis[p] + 1);
        vis[p] = true;
        Fo(v, n) if (w[p][v]) chkmin(dis[(v + dis[p] - 1) % n + 1], dis[p] + w[p][v]);
    }
    dis[s] = 0;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
    freopen("1528d.out", "w", stdout);
#endif

    int i, u, v;

    fc(w, 0x3f);

    read(n, m);
    Fo(i, m) {
        read(u, v);
        read(w[u + 1][v + 1]);
    }

    Fo(u, n) {
        dijkstra(u);
        Fo(i, n) write_(dis[i]);
        writeln();
    }

    return 0;
}