#include<fstream.h>

#define NrMax 1000
#define INF 1000000


int C[NrMax][NrMax],n,m,min,a[NrMax][NrMax],tata[NrMax],viz[NrMax],d[NrMax];

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

void initializare(int A[NrMax][NrMax])
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
				C[i][j]=INF;

}

void citire()
{
	int i,cost,x,y;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		a[x][y]=1;
		fin>>cost;
		C[x][y]=cost;
	}
}

void dijsktra(int x0)
{
	int i,k,ok;
	for(i=1;i<=n;i++)
	{
		tata[i]=x0;
		viz[i]=0;
		d[i]=C[x0][i];
	}
	
	viz[x0]=1;
	ok=1;
	tata[x0]=0;
	while(ok==1)
	{
		min=INF;
		for(i=1;i<=n;i++)
		{
			if(d[i]<min && viz[i]==0)
			{
				min=d[i];
				k=i;
			}
		}
		
		if(min!=INF)
		{
			for(i=1;i<=n;i++)
			{
				viz[k]=1;
				if(viz[i]==0 && d[i]>d[k]+C[k][i])
				{
					d[i]=d[k]+C[k][i];
					tata[i]=k;
				}
			}
		}
		else 
			ok=0;
	}
}

void afisare()
{
	int i;
	for(i=1;i<=n;i++)
		fout<<tata[i]<<" ";
	fout<<'\n';
}

void drum(int x)
{
	if(tata[x]!=0)
	{
		drum(tata[x]);
		fout<<" "<<x;
	}
	else
		fout<<x;
}
int main()
{
	int i;
	fin>>n>>m;
	initializare(C);
	citire();
	dijsktra(1);
	
	//afisare();
	for(i=2;i<=n;i++)
		fout<<d[i]<<" ";
	
	fout<<'\n';
	fout.close();
	return 0;
}