#include <stdio.h>
#define nod 50005
#define muchie 250005
#define inf 2000000000
struct legaturi{int vecin,lg;};
legaturi v[muchie];
int next[muchie],lista[nod],d[nod],heap[nod],ind[nod],k;
int tata(int p){return (p-1)/2;}
int fiust(int p){return 2*p+1;}
int fiudr(int p){return 2*p+2;}
void schimba(int p,int q){
    int aux=heap[p];
    heap[p]=heap[q];
    heap[q]=aux;
    ind[heap[p]]=p;
    ind[heap[q]]=q;
}
void urcare(int p){
    while(p>0&&d[heap[p]]<d[heap[tata(p)]]){
        schimba(p,tata(p));
        p=tata(p);
    }
}
void coborare(int p){
    bool pp=true;
    int st,dr;
    while(pp==true&&fiust(p)<k){
        pp=false;
        st=fiust(p);
        dr=fiudr(p);
        if(dr<k&&d[heap[dr]]<d[heap[st]])
            st=dr;
        if(d[heap[st]]<d[heap[p]]){
            schimba(st,p);
            pp=true;
        }
        p=st;
    }
}
void adaugare(int x){
    heap[k]=x;
    ind[x]=k;
    urcare(k);
    k++;
}
void stergere(int x){
    int p=ind[x];
    schimba(k-1,p);
    k--;
    if(d[heap[p]]<d[heap[tata(p)]])
        urcare(p);
    else
        coborare(p);
}
int main(){
    FILE *fin,*fout;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    int i,n,m,poz,elem;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fin,"%d%d%d",&elem,&v[i].vecin,&v[i].lg);
        if(lista[elem]==0)
            lista[elem]=i;
        else{
            next[i]=lista[elem];
            lista[elem]=i;
        }
    }
    d[1]=0;
    for(i=2;i<=n;i++){
        d[i]=inf;
        ind[i]=-1;
    }
    adaugare(1);
    while(k!=0){//k=nr elem in heap
        elem=heap[0];
        stergere(heap[0]);
        poz=lista[elem];
        while(v[poz].vecin!=0){
            if(d[elem]+v[poz].lg<d[v[poz].vecin]){
                d[v[poz].vecin]=d[elem]+v[poz].lg;
                if(ind[v[poz].vecin]!=-1){
                    urcare(ind[v[poz].vecin]);
                    coborare(ind[v[poz].vecin]);
                }
                else
                    adaugare(v[poz].vecin);
            }
            poz=next[poz];
        }
    }
    for(i=2;i<=n;i++)
        if(d[i]==inf)
            fprintf(fout,"0 ");
        else
            fprintf(fout,"%d ",d[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}