#include<fstream.h>
#include<stdlib.h>
#define nmax 50000
#define inf 2000
int *c[nmax];
long n,m,l[nmax];


void citire()
{
	ifstream fin("dijkstra.in");
	int cost;
	long i,j,x,y;

	fin>>n>>m;
	for(i=1;i<=n;i++)
		c[i]=(int*)realloc(c[i],n*sizeof(int));
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			c[i][j]=inf;
	for(i=1;i<=m;i++)
		{
			fin>>x>>y>>cost;
			c[x][y]=cost;
		}
	for(i=1;i<=n;i++)
		l[i]=c[1][i];
	fin.close();
}


void det()
{
	int v[nmax];long dmin,vfmin,i,j;
	l[1]=0;
	v[1]=1;

	for(j=1;j<n;j++)
	 {
		dmin=inf;
		for(i=1;i<=n;i++)
			if(!v[i]&&dmin>l[i])
					{dmin=l[i];vfmin=i;}
		v[vfmin]=1;
		for(i=1;i<=n;i++)
			if(!v[i]&&l[i]>dmin+c[vfmin][i])
				l[i]=dmin+c[vfmin][i];
	 }
}


void afisare()
{
	int i;
	ofstream fout("dijkstra.out");
	for(i=2;i<=n;i++)
		fout<<l[i]<<' ';
	fout<<'\n';
	fout.close();
}

int main()
{
	citire();
	det();
	afisare();
	return 0;
}