#include<stdio.h>
#include<iostream>

using namespace std;

FILE *c,*d;
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=fopen("dijkstra.in","r");
	d=fopen("dijkstra.out","w");
	fscanf(c,"%d %d",&n,&m);
	for(i=1;i<=m;i++)	
		fscanf(c,"%d %d %d",&v1[i],&v2[i],&cost[i]);
	dijkstra();
	for(i=2;i<=n;i++)
		if(l[i]==-1)
			fprintf(d,"0 ");
		else
			fprintf(d,"%d ",l[i]);
	fclose(c);
	fclose(d);
	return 0;
}