#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 605
using namespace std;
int n,m,h[N],tot;
struct edge{int to,nxt,val;}e[N*N];
void add(int x,int y,int z){e[++tot].nxt=h[x];h[x]=tot;e[tot].to=y;e[tot].val=z;}
int d[N],v[N],w[N];
int g(int x){
	return (x-1)%n+1;
}
void dij(int s){
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));d[s]=0;
	rep(t,1,n){
		int x=0;
		rep(j,1,n)if(!v[j]&&(!x||d[j]<d[x]))x=j;
		v[x]=1;
		//cout<<"ss "<<x<<endl;
		memset(w,0x3f,sizeof(w));
		for(int i=h[x];i;i=e[i].nxt){
			int ed=g(e[i].to+d[x]);
			//cout<<"Edge "<<x<<" "<<ed<<endl;
			w[ed]=min(w[ed],d[x]+e[i].val);
		}
		rep(i,1,n*2)w[g(i+1)]=min(w[g(i+1)],w[g(i)]+1);
		rep(i,1,n)d[i]=min(d[i],w[i]);
	}
	rep(i,1,n)printf("%d ",d[i]);putchar('\n');
}
signed main(){
	scanf("%d%d",&n,&m);
	rep(i,1,m){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		add(x+1,y+1,z);
	}
	rep(i,1,n)dij(i);
	return 0;
}