#include <fstream.h>
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int A[250000][250000], cost[250000], inainte[50000], viz[50000],n,m;

void citire_graf()
{		
	int x,y,c;
	f>>n>>m;
	for(int i=1;i<=m;i++)
	{	
		f>>x>>y>>c;				
		A[x][y]=A[y][x]=c;
	}	
}

void afis_drum(int v)
{
	if(v!=0){
		afis_drum(inainte[v]);
		g<<v<<" ";
	}
}





void drumuri_minime()
{
	int s,x,i,p,min;
	s=1;
	viz[s]=1;
	for(i=1;i<=n;i++)
	{
		cost[i]=A[s][i];
		inainte[i]=s;
	}
	inainte[s]=0;
	for(p=1;p<=n;p++)
	{	
		min=50000;
		for(i=1;i<=n;i++)
			if(viz[i]==0 && cost[i]!=0 && cost[i]<min)
			{
				min = cost[i];
				x=i;
			}
			viz[x]=1;		
		for(i=1;i<=n;i++)
			if(viz[i]==0 && A[x][i])
				if(cost[x] + A[x][i] < cost[i] || cost[i]==0)
				{
					cost[i]=cost[x]+A[x][i];
					inainte[i]=x;
				}
	}
	for(i=2;i<=n;i++)
		g<<cost[i]<<" ";
	//afiseaza_vectori();
}

int main()
{		
	citire_graf();
	drumuri_minime();	
}