#include<fstream>
#define infinit 1000000000
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n,m,c[1200][1200],t[1200],s[1200],d[1200];

void citire(){
	in>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j)
				c[i][j]=infinit;
	for(int i=1;i<=m;i++){
		int x,y,ct;
		in>>x>>y>>ct;
		c[x][y]=ct;
	}
}

void dijkstra(int r){
	int poz;
	for(int i=1;i<=n;i++){
		d[i]=c[r][i];
		
		if(d[i]==0&&i!=r)
			d[i]=infinit;
		if(d[i]<infinit)
			t[i]=r;
		
	}
	t[r]=0;
	s[r]=1;
	for(int j=1;j<n;j++){
		int min=infinit;
		for(int i=1;i<=n;i++)
			if(!s[i])
				if(d[i]<min){
					poz=i;
					min=d[i];
				}
		
		s[poz]=1;
		for(int i=1;i<=n;i++)
			if(!s[i]&&c[poz][i]<infinit){
				int sc=d[poz]+c[poz][i];
				if(sc<d[i]){
					d[i]=sc;
					t[i]=poz;
				}
			}
	}
}

void drum(int x){
	if(x){
		drum(t[x]);
		out<<x<<" ";
	}
}

int main(){
	citire();
	int r=1;

	dijkstra(r);
	for(int i=2;i<=n;i++)
		if(d[i]>=infinit)
			out<<0<<" ";
		else out<<d[i]<<" ";
	out<<endl;
	for(int i=2;i<=n;i++)
		if(d[i]<infinit)
			dijkstra(i);
	out<<endl;
	
return 0;
}