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

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

int dist[Nmax], h[Nmax], ph[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++)
        dist[i] = inf;
    dist[1] = 0;
    //constructie heap
    
    int NH = 0;
    for(int i=1;i<=N;i++){
        h[++NH] = i;
        ph[i] = NH;
        
        int j = NH;
        while(j/2 && dist[h[j]] < dist[h[j/2]]){
            h[j/2] ^= h[j], h[j] ^= h[j/2], h[j/2] ^= h[j];
            ph[h[j/2]] = j/2;
            ph[h[j]] = j;
            j>>=1;
        }
    }
    
    //dijkstra
    for(int i=1;i<=N;i++){
        int care = h[1];
        viz[care] = 1;

        h[1] ^= h[NH], h[NH] ^= h[1], h[1] ^= h[NH];
        ph[h[NH]] = NH;
        ph[h[1]] = 1;

        NH--;
        
        int k = 1;
        while(1){
            int fiu = k<<1;
            if(fiu > NH) break;
            if(fiu+1 <= NH && dist[h[fiu+1]] < dist[h[fiu]]) fiu ++;
            if(dist[h[k]] < dist[h[fiu]]) break;
            
            h[fiu] ^= h[k], h[k] ^= h[fiu], h[fiu] ^= h[k];
            ph[h[fiu]] = fiu;
            ph[h[k]] = k;

            k = fiu;
        }
        
        for(list p = a[care];p;p=p->next)
            if(!viz[p->vec] && dist[p->vec] > dist[care] + p->cost){
                dist[p->vec] = dist[care] + p->cost;
                
                int j = ph[p->vec];
                while(j/2 && dist[h[j]] < dist[h[j/2]]){
                    h[j/2] ^= h[j], h[j] ^= h[j/2], h[j/2] ^= h[j];
                    ph[h[j/2]] = j/2;
                    ph[h[j]] = j;

                    j>>=1;
                }
            }
    }
    
    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;
    
}