#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 fratelui
	} 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
    int extrag_heap(struct nod n[nmax], int h[nmax], int *e){
 	    int v=h[1];
		n[v].ph=0; //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
		{
		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; //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[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

   return 0;
   }