#include <stdio.h>
#include <string.h>

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

#define sint unsigned short

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

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

void initializare()
{
     memset(bell,NR,sizeof(bell));
     bell[1] = 0;
	coada[1]=1;
	v[1] = 1;     
}

void adauga(sint x, sint y, sint c)
{
	elem *current=new elem;
	current->nod=y;
	current->cost=c;
     current->next=p[x];
	p[x]=current;
	//inutil iful ala ... ;)
}

void relax(int x)
{
	elem *current=p[x];
	while(current)//NULL inseamna 0 se compara valoare de adevar a propozitii cu 0 in loc sa compare direct ... ;)
    	{
			if(bell[x]+current->cost<bell[current->nod])
				{
					bell[current->nod]=bell[coada[inceput]]+current->cost;
					if (v[current->nod] == 0) //nmu bagi un nod de doua ori in coada deodata ... adica sa exista maxim 1 singura data in coada
                         {
                              coada[++sfarsit]=current->nod;
                              v[current->nod] = 1;
                         }                              
				}
			current=current->next;
		}
}


void sol()
{
	while(inceput<=sfarsit)
		{
			relax(coada[inceput]);
			v[coada[inceput]] = 0;
     		++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();
	sol();
	for(i=2;i<=n;++i)
		{
			if(bell[i]!=NR)
				printf("%d ",bell[i]);
			else
				printf("0 ");
			//cea mai probabila chestie se puen prima ;)	
		}
	return 0;
}