#include <fstream>
#include <vector>
using namespace std;
#define dim 2000
#define inf 0x3f3f3f
int cost[dim][dim],t[dim],mat[dim];
long d[dim];
bool s[dim];

vector <int> v[dim][2];


int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	
	int n,m,a,b,c,i;
	
	fin>>n >>m;
	
	for(i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			cost[i][j]=inf;
	
	for(i=1;i<=m;++i)
	{
		fin>>a >>b >>c;
		cost[a][b]=c;
		add(v[a],b,c);
		add(v[b],a,c);
		++mat[a];
	}
	
	for(i=1;i<=n;++i)
	{
		for(int j=0;j<mat[i]-1;++j)
			fout<<v[i][j][0] <<" "<<v[i][j][1]<<" ";
		if(mat[i]!=0)
		fout<<'\n';
	}
	
	s[1]=1;
	for(i=1;i<=n;++i)
	{
		d[i]=cost[1][i];
		if(d[i]!=inf)
			t[i]=1;
	}
	

	for(i=2;i<=n;++i)
	{
		int min=inf,x=0,j;
		
		for(j=2;j<=n;++j)
			if(s[j]==0 && d[j]<min)
			{
				min=d[j];
				x=j;
			}
		
		if(x!=0)
		{	
			s[x]=1;
		for(j=2;j<=n;++j)
			if(d[j]>d[x]+cost[x][j])
			{
				d[j]=d[x]+cost[x][j];
				t[j]=x;
			}
		}
	}
	
	for(i=2;i<=n;++i)
	{
		if(d[i]!=inf)
		fout<<d[i]<<" ";
		else
			fout<<"0"<<" ";
	}
	
	
	return 0;
}