#include<stdio.h>
#include<fstream>

using namespace std;

ifstream c("dijkstra.in");
ofstream d("dijkstra.out");

int n,m,l[50001],v1[250001],v2[250001],cost[250001];

void dijkstra()
{	register int i;
	bool k=1;
	for(i=1;i<=n;i++)
		l[i]=-1;
	l[1]=0;
	while(k==1)	{
		k=0;
		for(i=1;i<=m;i++)
			if(l[v1[i]]>-1&&(l[v2[i]]==-1||l[v2[i]]>l[v1[i]]+cost[i]))	{
				l[v2[i]]=l[v1[i]]+cost[i];
				k=1;
			}
	}
}

int main()
{	int i;
	c>>n>>m;
	for(i=1;i<=m;i++)	
		c>>v1[i]>>v2[i]>>cost[i];
	dijkstra();
	for(i=2;i<=n;i++)
		if(l[i]==-1)
			d<<"0 ";
		else
			d<<l[i]<<" ";
	return 0;
}