#include<fstream.h>

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

int n,m,a[1000][1000],s[1000],t[1000],min,poz;
long d[2000];

int main()
{       int x,y,z,i,j;


	fin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=32000;
	for(i=1;i<=m;i++)
	{	fin>>x>>y>>z;
		a[x][y]=z;
	}
	s[1]=1;
	for(i=1;i<=n;i++)
	{	d[i]=a[1][i];
		if(i!=1) if(d[i]<32000) t[i]=1;
	}
	
	
	
	for(i=1;i<n;i++)
	{	min=32000;
		for(j=1;j<=n;j++)
			if(s[j]==0)
				if(d[j]<min) { min=d[j];
					       poz=j;
					     }
		s[poz]=1;
		for(j=1;j<=n;j++)
				if(d[j]>d[poz]+a[poz][j])
				{	d[j]=d[poz]+a[poz][j];
					t[j]=poz;
				}
	}
	for(i=2;i<=n;i++)
		fout<<d[i]<<" ";
	fin.close();
	fout.close();
	return 0;
}