#include <stdio.h>
#include <stdlib.h>
FILE *f1,*f2;
const int inf=1<<30;
typedef struct graf{
    int index,val;
    struct graf *next;
}graf;
graf *nod[50001];
int min_ind[50001],min_val[50001],vis[50001],ad[50001],cnt=0,poz[50001];
void add(int nod1,int nod2,int val){
    graf *q=(graf *)malloc(sizeof(graf*));
    if(q==NULL){
        exit(1);
    }
    q->index=nod2;
    q->next=nod[nod1];
    q->val=val;
    nod[nod1]=q;
}
void initial(int n){
    min_val[0]=0;
    ad[0]=1;
    int i;
    min_ind[0]=0;
    vis[0]=0;
    for (i=1;i<n;i++){
        min_val[i]=inf;
        vis[i]=0;
        ad[i]=0;
    }
}
void parcurge_drumuri(int index){
    vis[index]=1;
    if (nod[index]==NULL) return;
    while(nod[index]->next!=NULL){
        if(vis[index]==0 && (min_val[index]+nod[index]->val)<min_val[nod[index]->index]){
            min_val[nod[index]->index]=min_val[index]+nod[index]->val;
            resort(nod[index]->index);
        }
        nod[index]=nod[index]->next;
    }
}
void resort(int i){
    if(ad[i]==0){
        adauga(i);
    }
    else{
        resorteaza(i);
    }
}
void adauga(int i){
    int c=0,j;
    while(c!=cnt+1 && min_val[min_ind[c]]<min_val[i]){
        c++;
    }
    for(j=cnt+1;j>c;j--){
        poz[min_ind[j]]++;
        min_ind[j]=min_ind[j-1];
    }
    min_ind[c]=min_val[i];
    poz[i]=c;
    ad[i]=1;
}
void resorteaza(int i){
    int c=poz[i]-1,j;
    while(min_val[min_ind[c-1]]>min_val[i]){
        c--;
    }
    for(j=poz[i];j>c;j--){
        min_ind[j]=min_ind[j-1];
        poz[min_ind[j]]++;
    }
    poz[i]=c;
}
void dijkstra(){
    int i=0;
    for(i=0;i<=cnt;i++){
        if (vis[i]!=0) parcurge_drumuri(min_ind[i]);
    }
    print();
}
void print(int n){
    int i;
    for (i=1;i<n-1;i++){
        if(vis[i]==1) fprintf(f2,"%d ",min_val[min_ind[i]]);
        else fprintf(f2,"0 ");
    }
    if(vis[n-1]==1) fprintf(f2,"%d",min_val[min_ind[n-1]]);
    else fprintf(f2,"0");
}
int main()
{
    f1=fopen("dijkstra.in","r");
    f2=fopen("dijkstra.out","w");
    if(f1==NULL && f2==NULL){
        exit(1);
    }
    int n,m,x,y,z;
    fscanf(f1,"%d",&n);
    fscanf(f1,"%d",&m);
    while (fscanf(f1,"%d",&x)!=EOF){
        fscanf(f1,"%d",&y);
        fscanf(f1,"%d",&z);
        add(x-1,y-1,z);
    }
    fclose(f1);
    fclose(f2);
    return 0;
}