#include<stdio.h>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define nmax (50*1000+1)
#define mmax (250*1000+1)
struct lista
	{
	int n,c,p; //nodul, costul si pozitia
	} l[mmax];
struct nod
	{
	int p,c; //pozitia din lista, si costul minim cu care se ajunge din pct 1.......nu avem nevoie si de tata, deoarece nu refacem traseul :P
	char viz; //vom sti daca nodul se afla sau nu il coada
	} n[nmax];
int nr;

//adaugam arcul (x,y) cu costul c
void add(struct lista l[mmax], struct nod n[nmax], int m, int x, int y, int c)
	{
	l[m].n=y; l[m].c=c; l[m].p=n[x].p; n[x].p=m;
	}

void citire(struct lista l[mmax], struct nod n[nmax], int *nr)
	{
	int i,m,x,y,c;
	scanf("%d %d\n",nr,&m);
	for(i=1;i<=m;i++) //luam fiecare arc
		{
		scanf("%d %d %d\n",&x,&y,&c); //arcul (x,y) cu costul c
		add(l,n,i,x,y,c); //adaugam in lista
		}
	}

void dfs(struct lista l[mmax], struct nod n[nmax], int x) //x - nodul din care se incepe parcurgerea
	{
	int ul;
	int coada[nmax], st, dr, e; //coada si capetele ei
	n[x].c=0; //are costul 0
	st=dr=1; e=1; coada[st]=x; n[x].viz=1; //initializam coada
	while(e) //cat timp avem elemente in coada
		{
		x=coada[st%nmax]; //luam elementul din coada
		ul=n[x].p; //pozitia din lista a fiului lui x
		while(ul) //cat timp x are copii in lista
			{
			if(n[x].c+l[ul].c<n[l[ul].n].c || n[l[ul].n].c==-1) //daca ajungem la nod cu un cost mai mic decat pana acum, sau daca nu am mai ajuns
				{
				n[l[ul].n].c=n[x].c+l[ul].c; //salvam noul cost cu care ajungem
				if(!n[l[ul].n].viz) //daca nu se afla deja in coada
					{
					n[l[ul].n].viz=1; //marcam k l-am adaugat in coada
					coada[(++dr)%nmax]=l[ul].n; e++; //il adaugam in coada
					}
				}
			ul=l[ul].p; //trecem la urmatorul copil al lui x
			}
		n[x].viz=0; st++; e--; //inaintam in coada
		}
	}

int main()
{
int i;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(l,n,&nr); //citim si salvam graful in memorie
for(i=1;i<=nr;i++) n[i].c=-1; //initializam initial costul -1
dfs(l,n,1); //parcurgem graful si aflam costurile minime din punctul 1
for(i=2;i<=nr;i++)
	if(n[i].c==-1) printf("%d "); //inseamna k nu se poate ajunge din 1
	else printf("%d ",n[i].c); //afisem costurile obtinute

fclose(stdin);
fclose(stdout);
return 0;
}