//Bellman-Ford cu coada 
//complexitate < O(M*N)

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

int dist[50005];
char viz[50005];

struct nod{int vec, cost; nod* next;};
typedef nod* lista;
lista a[50005];

struct elem{int nod; elem* next;};
typedef elem* coada;
coada Q,Qf;

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,l;
        fscanf(fin,"%d%d%d",&x,&y,&l);
        
        lista aux = new nod;
        aux -> vec = y;
        aux -> cost = l;
        aux -> next = a[x];
        a[x] = aux;
        
    }
        
    for(int i=1;i<=N;i++) 
        dist[i]=inf;
    dist[1]=0;
    
    //adaugare sursa in coada
    Q = Qf = new elem;
    Q->nod = 1;
    Q->next = NULL;
    viz[1] = 1;

    //procesare coada cu bellman ford
    while(Q){
        
        //procesez primul element
        int crt = Q->nod;
        for(lista p = a[crt];p;p=p->next)
            if(dist[p->vec] > p->cost + dist[crt]){
                dist[p->vec] = dist[crt] + p->cost;
                
                //verificare dak vecinul se afla in coada
                if(viz[p->vec]==0){
                    viz[p->vec] = 1;                
                    Qf->next = new elem;
                    Qf = Qf -> next;
                    Qf->nod = p->vec;
                    Qf -> next = NULL;
                }
            }
                
        //scot din coada primul element
        viz[crt] = 0;
        coada aux = Q;
        Q=Q->next;
        delete aux;
                
    }

    for(int i=2;i<=N;i++)
        if(dist[i] < inf)
            fprintf(fout,"%d ",dist[i]);
        else
            fprintf(fout,"0 ");
            
    fclose(fin);
    fclose(fout);
    return 0;
    
}