#include <stdio.h>
#define INF -1
struct edge{
    int x;
    int y;
    int c;} e[250001];
int d[50001],n,m;

void read_data(){
    int i;
        freopen("dijkstra.in","r",stdin);
        freopen("dijkstra.out","w",stdout);
            scanf("%d%d",&n,&m);
            for(i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
}

void process(){
    int i;
    bool yes=true;
        d[1]=0;
        for(i=2;i<=n;i++)d[i]=INF;
    while(yes){
        yes=false;
        for(i=1;i<=m;i++)
        if(d[e[i].x]!=INF&&d[e[i].y]==INF||d[e[i].y]>d[e[i].x]+e[i].c){
            d[e[i].y]=d[e[i].x]+e[i].c;
            yes=true; };
    }
}

void write_data(){
    int i;
        for(i=2;i<=n;i++)
        if(d[i]!=INF)printf("%d ",d[i]);else printf("%d ",0);
}

int main(){
    read_data();
    process();
    write_data();
}