#include<fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int m,n,a,b,cost[50005],viz[50005],x,c,A[50001][5001],j;

int chestie( int p )
{
	int minim,i;
	minim=0;
	p=0;
	for(i=2;i<=n;i++)
	{
		if(viz[i]==0 && cost[i]&&(minim>=cost[i]||minim==0)) minim=cost[i],p=i;
	}
	return p;
}

void prel(int y)
{
	viz[y]=1;
	for(int i=1;i<=n;i++)
	{
		if(viz[i]==0&&A[y][i]!=0)
			if(cost[y]+A[y][i]<cost[i]||cost[i]==0) cost[i]=cost[y]+A[y][i];
	}
	
}

int main()
{
	f>>n>>m;
	viz[1]=1;
	for(j=1;j<=m;j++)
	{
		f>>a>>b>>c;
		if(a==1) cost[b]=c;
		//else if(b==1) cost[a]=c;
		A[a][b]=c;
	}
	
	x=chestie(1);
	while(x!=0)
	{
		//g<<x<<'*';
		prel(x);
		x=chestie(1);
	}
	
	for(j=2;j<=n;j++) g<<cost[j]<<' ';
	
	f.close();
	g.close();
	return 0;
}