//Dijkstra O(N^2)

#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 main(){
    
    FILE *fin = fopen("dijkstra.in","r"),
         *fout = fopen("dijkstra.out","w");
         
    int N,M;
    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;
    }
    
    for(int i=1;i<=N;i++)
        d[i] = inf, viz[i]=0;
        
    //initializare
    d[1]=0;
    for(int k=1;k<=N;k++){
        
        int min = inf, poz = 0;
        for(int i=1;i<=N;i++)
            if(viz[i]==0 && d[i] < min)
                min = d[i], poz=i;
                
        viz[poz] = 1;
        
        //relaxarea muchii vecine nodului tocmai introdus (poz)
        for(list p = a[poz];p;p=p->next)
            if(d[p->vec] > d[poz] + p->cost)
                d[p->vec] = d[poz] + p->cost;
            
    }
    
    for(int i=2;i<=N;i++)
        fprintf(fout,"%d ",d[i]);
    fprintf(fout,"\n");
    
    fclose(fin);
    fclose(fout);
    return 0;
}