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

int dist[Nmax], h[Nmax], ph[Nmax];
char viz[Nmax];
int *vec[Nmax], *cost[Nmax];
int Nvec[Nmax];

void intersc(int i,int j){

    h[i] ^= h[j], h[j] ^= h[i], h[i] ^= h[j];
    ph[h[i]] = i;
    ph[h[j]] = j;

}

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);
        Nvec[x]++;
    }
    
    for(int i=1;i<=N;i++){
        vec[i] = new int[Nvec[i] + 4];
        cost[i] = new int[Nvec[i] + 4];
        Nvec[i] = 0;
    }
    
    fclose(fin);
    
    fin = fopen("dijkstra.in","r");
    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);
        vec[x][++Nvec[x]] = y;
        cost[x][Nvec[x]] = c;
    }
    
    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]]){
            intersc(j,j/2);
            j>>=1;
        }
    }
    
    //dijkstra
    for(int i=1;i<=N;i++){
        int care = h[1];
        viz[care] = 1;
        
        intersc(1,NH);
        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;
            
            intersc(k,fiu);
            k = fiu;
        }
        
        for(int v = 1;v<=Nvec[care];v++)
            if(!viz[vec[care][v]] && dist[vec[care][v]] > dist[care] + cost[care][v]){
                dist[vec[care][v]] = dist[care] + cost[care][v];
                
                int j = ph[vec[care][v]];
                while(j/2 && dist[h[j]] < dist[h[j/2]]){
                    intersc(j,j/2);
                    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;
    
}