#include <stdio.h>

#define Nmax 100001
#define NR 500000000
#define Cmax 500000

struct elem{
	int nod,cost;
	elem *next;
};
elem *p[Nmax];

int bell[Nmax],n,m,coada[Cmax],inceput=1,sfarsit=1;

void initializare()
{
	int i;
	for(i=2;i<=n;++i)
		bell[i]=NR;
}

void adauga(int x, int y, int c)
{
	elem *current=new elem;
	current->nod=y;
	current->cost=c;
	if(p[x]==NULL)
		{
			p[x]=current;
			current->next=NULL;
		}
	else
		{
			current->next=p[x];
			p[x]=current;
		}
}

void relax(int x)
{
	elem *current=p[x];
	while(current!=NULL)
    	{
			if(bell[x]+current->cost<bell[current->nod])
				{
					bell[current->nod]=bell[coada[inceput]]+current->cost;
					coada[++sfarsit]=current->nod;
				}
			current=current->next;
		}
}


void sol()
{
	while(inceput<=sfarsit)
		{
			relax(coada[inceput]);
			++inceput;
		}
}

int main()
{
	int x,y,c,i;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
		{
			scanf("%d%d%d",&x,&y,&c);
			adauga(x,y,c);
		}
	initializare();
	coada[1]=1;
	sol();
	for(i=2;i<=n;++i)
		{
			if(bell[i]==NR)
				printf("0 ");
			else
				printf("%d ",bell[i]);
		}
	return 0;
}