#include<stdio.h>
#define infinit 2000000000
struct nod{
    int inf,c;
    nod *urm;
}*l[50005];
FILE *f;
int n,nh,m,x[50005],d[50005],t[50005],poz[50005];
void cit(){
    FILE *f;
    nod *p;
    int a,b,c,i;
    f=fopen("dijkstra.in","r");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=n;i++)
        l[i]=0;
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&a,&b,&c);
        p=new nod;
        p->inf=b;
        p->c=c;
        p->urm=l[a];
        l[a]=p;
    }
    fclose(f);
}
void swap(int i,int j){
    int aux;
    poz[x[i]]=j;
    poz[x[j]]=i;
    aux=x[i];
    x[i]=x[j];
    x[j]=aux;
}
void HeapUp(int k){
    if(k<=1)
        return;
    if(d[x[k]]<d[x[k/2]]){
        swap(k,k/2);
        HeapUp(k/2);
    }
}
void HeapDw(int r,int k){
    int st,dr,i;
    if(2*r<=k){
        st=d[x[2*r]];
        if(2*r+1<=k)
            dr=d[x[2*r+1]];
        else
            dr=st+1;
        if(st<dr)
            i=2*r;
        else
            i=2*r+1;
        if(d[x[r]]>d[x[i]]){
            swap(i,r);
            HeapDw(i,k);
        }
    }
}
void BuildH(int k){
    int i;
    for(i=1;i<=k;i++)
        HeapUp(i);
}
int scoate_heap(){
    swap(1,nh);
    poz[x[nh]]=0;
    nh--;
    HeapDw(1,nh);
    return x[nh+1];
}
void dijkstra(){
    int i,k;
    nod *p;
    for(i=1;i<=n;i++){
        x[i]=poz[i]=i;
        t[i]=0;
        d[i]=infinit;
    }
    d[1]=0;
    BuildH(n);
    nh=n;
    while(nh>0){
        k=scoate_heap();
        p=l[k];
        while(p){
            if(d[p->inf]>d[k]+p->c){
                d[p->inf]=d[k]+p->c;
                t[p->inf]=k;
                HeapUp(poz[p->inf]);
            }
            p=p->urm;
        }
    }
}
void lant(int i){
    if(i!=0){
        lant(t[i]);
        fprintf(f,"%d ",i);
    }
}
void afis(){
    int i;
    f=fopen("dijkstra.out","w");
    for(i=2;i<=n;i++)
        fprintf(f,"%d ",d[i]==infinit ? 0:d[i]);
    fclose(f);
}
int main(){
    cit();
    dijkstra();
    afis();
    return 0;
}