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

int cost[50000], viz[50000],n,m;
int A[10000][10000];

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

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];
	for(p=1;p<=n-2;p++)
	{	
		min=250000;
		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];
	}
	for(i=2;i<=n;i++)
		g<<cost[i]<<" ";	
}

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