#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(i=(a);i<=(b);++i)
#define per(i,a,b) for(i=(a);i>=(b);--i)
#define REP(i,a,b) for(i=(a);i< (b);++i)
#define PER(i,a,b) for(i=(a);i> (b);--i)
#define ERR(...) fprintf(stderr,__VA_ARGS__)
template<class T>inline void cmn(T &x,const T &a){if(a<x)x=a;}
template<class T>inline void cmx(T &x,const T &a){if(x<a)x=a;}
template<class T>inline bool bmn(T &x,const T &a){if(a<x){x=a;return true;}else return false;}
template<class T>inline bool bmx(T &x,const T &a){if(x<a){x=a;return true;}else return false;}
const ll p=998244353ll,pp=p*p;const int ps2=p-2ll;
inline void add(ll &x){if(x>= p)x-=p ;}
inline void sub(ll &x){if(x<0ll)x+=p ;}
inline void adp(ll &x){if(x>=pp)x-=pp;}
inline void sup(ll &x){if(x<0ll)x+=pp;}
inline ll expo(ll a,int b=ps2,ll m=p){
	ll s=1ll;
	while(b){
		if(b&1)s=s*a%p;
		b>>=1; a=a*a%p;
	}
	return s;
}

inline void ac();
//inline void in();int main(){in();int t;scanf("%d",&t);while(t--)ac();return 0;}
//int main(){int t;scanf("%d",&t);while(t--)ac();return 0;}
int main(){ac();return 0;}

const int MAXN=605;
const ll inf=1000000000000000000ll;
bool V[MAXN];
ll D[MAXN],E[MAXN][MAXN];
inline void ac(){
	int n,m,i,j,k;
	scanf("%d%d",&n,&m);
	REP(i,0,n)REP(j,0,n)E[i][j]=inf;
	while(m--){
		scanf("%d%d%d",&i,&j,&k);
		cmn(E[i][j],(ll)k);
		//ERR("%d --%d-> %d\n",i,k,j);
	}
	int aM;ll M;
	REP(k,0,n){
		REP(i,0,n)D[i]=E[k][i];
		REP(i,0,n)V[i]=true;
		//ERR("\n\n\n\nk=%d\n",k);
		REP(j,0,n){
			M=inf;
			REP(i,0,n)if(V[i]&&bmn(M,D[i]))aM=i;
			V[aM]=false;
			//ERR("Dis(%d) = %lld\n",aM,M);
			if((i=aM+1)==n)i=0;if(V[i])cmn(D[i],M+1ll);
			//ERR("%d --1-> %d\n",aM,i);
			//REP(i,0,n)ERR("%d --%lld-> %d\n",aM,E[aM][i],(i+M)%n);
			REP(i,0,n)cmn(D[(i+M)%n],M+E[aM][i]);
		}
		D[k]=0ll;
		REP(i,0,n)printf("%lld ",D[i]);puts("");
	}
}
/*
Suppose we did normal dijkstra, the only case that might be missed is when we wait in a vertex for some time.
To handle the 'waiting' concept, we can add 𝑛  fake edges, 𝑖-th of which is from the 𝑖-th vertex to the (𝑖  + 1 mod 𝑛)-th vertex with weight equal to one.
Note that unlike the cannons, fake edges do not rotate.
It can be proved that doing dijkstra in the new graph is sufficient if we guarantee that the first used edge is not fake.
We can map waiting for 𝑥  seconds and then using an edge to go to 𝑢  from 𝑣  to using a cannon and then using 𝑥  fake edges to go to 𝑢  from 𝑣.
Also due to the strict time limit you should use the O(𝑛  ^ 2) variant of dijkstra.
complexity: O(𝑛  ^ 3)
*/
