#include<bits/stdc++.h>
using namespace std;
const int siz = 1e5+5;
vector<pair<int,int>>g[siz];
int t,n,m,k,ans,dist[siz],need[siz];
bool vis[siz];
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,c; cin>>x>>y>>c; g[x].push_back({y,c});
    }
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<=n;j++)
        {
            dist[j] = 1e9+n; vis[j] = 0;
        }
        dist[i] = 0; dist[n] = 2e9+5;
        for(int z = 0;z<n;z++)
        {
            int u = n;
            for(int j = 0;j<n;j++) if(!vis[j] and dist[j]<dist[u]) u = j;
            for(int j = 0;j<2*n;j++) need[j] = 2e9;
            int sofar = dist[u];
            for(auto x:g[u])
            {
                int v = x.first,cost = x.second;
                need[(sofar+v)%n] = min(need[(sofar+v)%n],cost);
            }
            for(int j = 1;j<2*n;j++) need[j] = min(need[j],1+need[j-1]);
            for(int nxt = 0;nxt<n;nxt++)
            {
                need[nxt] = min(need[nxt], need[nxt + n]);
                dist[nxt] = min(dist[nxt],sofar+need[nxt]);
            }
            vis[u] = 1;
        }
        for(int j = 0;j<n;j++) cout<<dist[j]<<" ";
        cout<<endl;
    }
}
