//Dijkstra cu heapuri O(NlogN)

#include<stdio.h>
#define Nmax 50005
#define inf 100000000

struct nod{int vec, cost; nod* next;};
typedef nod* list;
list a[Nmax];

int d[Nmax];
char viz[Nmax];
int heap[Nmax], pozh[Nmax];

void swap(int i, int j){
    int aux;
    aux = heap[i]; heap[i] = heap[j]; heap[j] = aux;
    pozh[heap[i]] = i; 
    pozh[heap[j]] = j;    
}

int main(){
    
    FILE *fin = fopen("dijkstra.in","r"),
         *fout = fopen("dijkstra.out","w");
         
    int N,M,nh;
    fscanf(fin,"%d%d",&N,&M);
    
    for(int i=1;i<=M;i++){
        int x,y,c;
        fscanf(fin,"%d%d%d",&x,&y,&c);
        
        list aux = new nod;
        aux->vec = y;
        aux->cost = c;
        aux->next = a[x];
        a[x]=aux;
    }
    
    //initializare
    for(int i=1;i<=N;i++)
        d[i] = inf, viz[i]=0, heap[i]=i, pozh[i]=i;
    d[1]=0;
    nh = N;
    
    //dijkstra pr-zis
    for(int k=1;k<=N;k++){

        //minimul se afla in radacina heapului
        int nod = heap[1];
        swap(1,nh);
        nh--;
        
        //reafacere proprietate heap 
        int i=1,fiu;
        while(1){
            fiu = 2*i;
            if(fiu > nh) break;
            if(fiu + 1 <= nh && d[heap[fiu+1]] < d[heap[fiu]]) fiu++;
            if(d[heap[i]] < d[heap[fiu]]) break;
            
            swap(i,fiu);
            i=fiu;                
        }
        
        //relaxare muchii vecini
        for(list p = a[nod];p;p=p->next)
            if(d[p->vec] > d[nod] + p->cost){
                d[p->vec] = d[nod] + p->cost;
                //s-a micsorat distanta deci trebuie verificata proprietatea heapului
                    
                int j=pozh[p->vec];
                while(j/2 && d[heap[j]] < d[heap[j/2]]){
                    swap(j,j/2);
                    j>>=1;    
                }
            }   
            
    }
    
    for(int i=2;i<=N;i++)
        if(d[i] < inf)
            fprintf(fout,"%d ",d[i]);
        else
            fprintf(fout,"0 ");
    fprintf(fout,"\n");
    
    fclose(fin);
    fclose(fout);
    return 0;
}