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

typedef long long LL;

const int N=600;
const LL INF=(1LL<<60)-1;

int Ri(){
  int x=0;
  char c=getchar();
  for (;c<'0'||c>'9';c=getchar());
  for (;c<='9'&&c>='0';c=getchar()) x=x*10+c-'0';
  return x;
}

int n,m;
LL a[N+9][N+9],e[N+9][N+9];

void into(){
  n=Ri();m=Ri();
  for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j) a[i][j]=e[i][j]=INF;
  for (int i=1;i<=m;++i){
	int x,y;
	LL v;
	x=Ri()+1;y=Ri()+1;v=Ri();
	a[x][y]=min(a[x][y],v);
  }
}

void Get_e(){
  for (int k=1;k<=n;++k)
	for (int i=1;i<=n;++i)
	  for (int j=0;j<n;++j) e[k][i]=min(e[k][i],j+a[k][(i-j+n-1)%n+1]);
}

int vis[N+9];

void Dijkstra(int st,LL *dis){
  for (int i=1;i<=n;++i) dis[i]=INF,vis[i]=0;
  dis[st]=0;
  for (int i=1;i<=n;++i){
	int k=0;
	for (int j=1;j<=n;++j)
	  if (!vis[j]&&(!k||dis[j]<dis[k])) k=j;
    vis[k]=1;
	for (int i=1;i<=n;++i){
	  int y=(i-dis[k]%n+n-1)%n+1;
	  if (dis[k]+e[k][y]<dis[i]) dis[i]=dis[k]+e[k][y];
	}
  }
}

LL ans[N+9][N+9];

void Get_ans(){
  for (int i=1;i<=n;++i) Dijkstra(i,ans[i]);
}

void work(){
  Get_e();
  Get_ans();
}

void outo(){
  for (int i=1;i<=n;++i){
	for (int j=1;j<=n;++j) printf("%d ",ans[i][j]);
	puts("");
  }
}

int main(){
  int T=1;
  //scanf("%d",&T);
  for (;T--;){
    into();
    work();
    outo();
  }
  return 0;
}