#include<bits/stdc++.h>
#define int long long
#define ld long double
#define fi first
#define se second
#define vll vector<int>
#define pii pair<int,int>
#define pb push_back
#define sz(v) (int)(v).size()
#define inf (int)(1e18)
#define md (int)(1e9+7)
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;++i)
using namespace std;

const int M = 2e5 + 10;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   	
   	int n,m;
   	cin>>n>>m;
   	int D[n][n];
   	rep(i,0,n)rep(j,0,n) D[i][j]=inf;
   	rep(i,0,m) {
   		int u,v,w;
   		cin>>u>>v>>w;
   		rep(j,0,n) {
   			D[u][(v+j)%n]=min(D[u][(v+j)%n],j+w);
   		}
   	}
   	vector<int> d(n);
   	bool vis[n];
   	rep(s,0,n) {
   		rep(j,0,n) d[j]=inf,vis[j]=0;
   		d[s]=0;
   		rep(i,0,n) {
   			int v=-1;
   			rep(j,0,n) {
   				if(!vis[j] and (v<0 or d[j]<d[v])) {
   					v=j;
   				}
   			}
   			if(d[v]==inf) break;
   			vis[v]=1;
   			int x=d[v]%n;
   			rep(j,0,n) {
   				d[j]=min(d[j],d[v]+D[v][j<x?j-x+n:j-x]);
   			}
   		}
   		rep(j,0,n) {
   			cout<<d[j]<<" ";
   		}
   		cout<<"\n";
   	}
   	
   	
    return 0;
}