//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn=666;

int n,m;
vector <pii> edge[maxn];
int pre[maxn][maxn],suf[maxn][maxn];
pq <pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
ll grid[maxn][maxn];
ll f[maxn];
bool mark[maxn];

void solve(int x) {
	memset(f,inf,sizeof(f));
	memset(mark,0,sizeof(mark));
	f[x]=0;
	rep(i,0,n) {
		int u=-1;
		rep(j,0,n) if (!mark[j]&&(u==-1||f[j]<f[u])) u=j;
		ll d=f[u];
		mark[u]=1;
		grid[x][u]=d;
		rep(v,0,n) {
			int tmp=(v-d%n+n)%n;
			ll dis = (ll)min(pre[u][tmp],n+suf[u][tmp+1]) + tmp + d;
			if (dis<f[v]) f[v]=dis;
		}
	}
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie();
	cin>>n>>m;
	rep(i,0,m) {
		int a,b,c;
		cin>>a>>b>>c;
		edge[a].pb(MP(b,c));
	}
	rep(i,0,n) {
		sort(ALL(edge[i]));
		int cur=0;
		rep(j,0,n) {
			pre[i][j]=(j==0?1100000000:pre[i][j-1]);
			if (cur<SZ(edge[i])&&edge[i][cur].fi==j) pre[i][j]=min(pre[i][j],-edge[i][cur].fi+edge[i][cur].se),cur++;
		}
		cur=SZ(edge[i])-1;
		suf[i][n]=1100000000;
		for (int j=n-1;j>=0;j--) {
			suf[i][j]=suf[i][j+1];
			if (cur>=0&&edge[i][cur].fi==j) suf[i][j]=min(suf[i][j],-edge[i][cur].fi+edge[i][cur].se),cur--;
		}
	}
	rep(i,0,n) solve(i);
	rep(i,0,n) {
		rep(j,0,n) cout<<grid[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}
