#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;
char v[Nmax];

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;
	current->next=p[x];
	p[x]=current;
}

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


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

#define DIM 10000
char buff[DIM];
int poz=0;
#define buffer fread(buff,1,DIM,stdin),poz=0

#define cit(x)                                         \
{                                                      \
     x = 0;                                            \
     while (buff[poz] < '0' || buff[poz] > '9')        \
     if (++poz == DIM) buffer;                         \
     while ('0'<=buff[poz] && buff[poz]<='9')          \
     {                                                 \
          x = x*10 + buff[poz] - '0';                  \
          if (++poz == DIM) buffer;                    \
     }                                                 \
}

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