#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<complex>
#include<cstdio>
#define initdp(a,b) for(int i=0;i<=a;i++)for(int j=0;j<=b;j++)dp[i][j]=-1;
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ppi pair<pii,int>
#define pip pair<int,pii>
#define ll long long
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define inf 2000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846
#define N 100005
#define mid(l,r) l+(r-l)/2
#define removeduplicates(vec) vec.erase( unique( vec.begin(), vec.end() ), vec.end() )
#define memset1(v) memset(v,-1,sizeof(v))
#define memset0(v) memset(v,0,sizeof(v))
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int ddx[8]={1,1,0,-1,-1,-1,0,1},ddy[8]={0,1,1,1,0,-1,-1,-1};
void mad(ll &a,ll b){a=(a+b)%mod;if(a<0)a+=mod;}
ll gcd(ll a,ll b){ if(!a)return b;return gcd(b%a,a);}
int w[605][605];
void solve(){
	int n,m;
	cin>>n>>m;
	vector<pii>ed[n];
	rep(i,n)rep(j,n)w[i][j]=inf;
	for(int i=0;i<m;i++){
		int u,v,c;
		cin>>u>>v>>c;
		for(int j=0;j<n;j++)w[u][(v+j)%n]=min(w[u][(v+j)%n],c+j);
		//ed[v].pb(pii(u,c));
	}
	rep(i,n)rep(j,n)ed[i].pb(pii(j,w[i][j]));
	for(int i=0;i<n;i++){
		vector<ll>d(n,inf1);
		priority_queue<pli>pq;
		d[i]=0;
		pq.push({0,i});
		while(!pq.empty()){
			ll curd=-pq.top().fi;
			int u=pq.top().se;
			pq.pop();
			if(d[u]<curd)continue;
			for(pii p:ed[u]){
				int v=(p.fi+curd)%n;
				ll c=p.se;
				if(d[v]>curd+c){
					d[v]=curd+c;
					pq.push({-curd-c,v});
				}
			}
		}
		for(int j=0;j<n;j++)cout<<d[j]<<" ";cout<<"\n";
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}