#include<stdio.h>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define inf ~(1<<31)
#define nmax (50*1000+1)
#define mmax (250*1000+1)
struct lista
	{
	int n,c,p; //nodul, costul, si pozitia lu frasu
	} l[mmax];
struct nod
	{
	int p,c,ph; //pozitia din lista, costul minim, si pozitia din heap
	} n[nmax];
int h[nmax], e; //min-heap-ul, si variabila ce retine numarul de elemente din heap
int nr; //numarul de noduri din graf

void schimba(int *a, int *b)
	{ int c=*a; *a=*b; *b=c; }

//adauga arcul (x,y) cu costul c in lista
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++)
		{
		scanf("%d %d %d\n",&x,&y,&c); //citim arcul (x,y) cu costul c
		add(l,n,i,x,y,c); //adaugam arcul in lista
		}
	}

//adaugam nodul x in heap
void add_heap(struct nod n[nmax], int h[nmax], int e, int x)
	{
	int fiu=e; //ultima pozitie
	int tata=fiu/2; //tatal fiului
	while(tata&&n[h[tata]].c>n[x].c) //cat timp are tata, si costul tatalui este mai mare
		{ h[fiu]=h[tata]; n[h[fiu]].ph=fiu; fiu=tata; tata=fiu/2; } //la fiu copiem tatal (salvam la nod pozitia din heap), fiul va deveni tata, si tata va fi tatal tatalui :))
	h[fiu]=x; n[h[fiu]].ph=fiu; //plasam nodul la pozitia corecta in heap, si marcam pozitia din heap la nod
	}

//extrage cel mai mic element din heap :P
int extrag_heap(struct nod n[nmax], int h[nmax], int *e)
	{
	int v=h[1]; n[v].ph=-1; //valoarea pe care o vom returna, si marcam k nu mai este in heap
	int x=h[*e]; *e-=1; //scoatem ultima valoare si o salvam in variabila....
	int tata=1;
	int fiu=tata*2;
	while(fiu<=*e) //cat timp mai exista fii :P
		{
		if(fiu<*e && n[h[fiu+1]].c<n[h[fiu]].c) fiu++; //e mai mic al doilea fiu
		if(n[h[fiu]].c<n[x].c) //daca copilul este mai mic
			{ h[tata]=h[fiu]; n[h[tata]].ph=tata; tata=fiu; fiu=tata/2; } //urcam fiul in sus, si coboram tatal
		else fiu=*e+1; //inseamna k am gasit pozitia unde trebuie plasat x, deci oprim cautarea
		}
	h[tata]=x; n[x].ph=tata; //plasam pe x la pozitia corecta
	return v; //returnam valoarea minima care am extraso la inceput din heap
	}

//atunci cand se modifica costul pentru un nod, trebuie sa vedem daca acel cost e mai mic decat costul lui taicasu
void reordonare_heap(struct nod n[nmax], int h[nmax], int fiu)
	{
	int tata=fiu/2;
	while(tata&&n[h[tata]].c>n[h[fiu]].c) //cat timp avem tata, si costul tatalui este mai mare
		{
		schimba(&h[tata],&h[fiu]); //inlocuim tatal cu fiul
		n[h[tata]].ph=tata; n[h[fiu]].ph=fiu; //modific si la noduri pozitia lor din heap
		fiu=tata; tata=fiu/2; //fiul devine tata.....si tatal este jumate din fiu:)
		}
	}

void initializare(struct lista l[mmax], struct nod n[nmax], int h[nmax], int nr, int *e, int x) //x-nodul din care se va face dijkstra
	{
	int i,ul=n[x].p; n[x].c=0; n[x].ph=-1; //catre punctul de plecare costul este 0
	for(i=1;i<=nr;i++) n[i].c=inf; //initial avem costul infinit
	while(ul) //cat timp x are copii :P
		{
		n[l[ul].n].c=l[ul].c; //salvam costul cu care putem ajunge la nod
		add_heap(n,h,*e+=1,l[ul].n); //adaugam nodul in heap
		ul=l[ul].p; //fratesu
		}
	}

//facem algoritmul pt heap-ul deja initializat
void dijkstra(struct lista l[mmax], struct nod n[nmax], int h[nmax], int *e)
	{
	int x,ul;
	while(*e) //cat timp avem elemente in heap
		{
		x=extrag_heap(n,h,e); //primesc nodul de cost minim din heap...si il scot din heap
		ul=n[x].p; //pozitia din lista
		while(ul) //cat timp x are copii
			{
			if(n[l[ul].n].c>=0 && n[x].c+l[ul].c<n[l[ul].n].c) //daca ajung cu un cost mai mic
				{
				n[l[ul].n].c=n[x].c+l[ul].c;
				if(!n[l[ul].n].ph) add_heap(n,h,*e+=1,l[ul].n); //daca nu este in heap, il adaugam
				else reordonare_heap(n,h,n[l[ul].n].ph); //s-a modificat costul nodului, deci trebuie sa il rearanjam in heap
				}
			ul=l[ul].p; //trecem la frasu
			}
		}
	}

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

citire(l,n,&nr); //citim si salvam graful
initializare(l,n,h,nr,&e,1); //facem initializarea pt dijkstra
dijkstra(l,n,h,&e); //apelam DIJKSTRA :> 
for(i=2;i<=nr;i++)
	if(n[i].c==inf) printf("0 "); //inseamna k nu se poate ajunge la acest punct
	else printf("%d ",n[i].c); //afisem costul nodului

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