#include<stdio.h>
#include<stdlib.h>
#define N 50001
#define usi unsigned short int
typedef struct O {
    usi o,c;
    struct O *u;
}G;
G *g[N];
int m;
usi n,k,t,h[N],d[N],f,w,u,p[N];
int main() {
    freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
    while(m--) {
        scanf("%d%d%d",&u,&w,&f);
        g[0]=(G*)malloc(sizeof(G));
        g[0]->o=w,g[0]->c=f,g[0]->u=g[u],g[u]=g[0];
    }
    for(u=2;u<=n;u++)
        d[u]=p[u]=N;
    for(p[1]=h[++k]=1;k;) {
        for(t=h[1],h[1]=h[k--],p[h[1]]=w=1;(w<<1)<=k;w=f) {
            f=w<<1;
            if(f<k&&d[h[f+1]]<d[h[f]])
                f++;
            if(d[h[w]]<=d[h[f]])
                break;
            h[w]^=h[f]^=h[w]^=h[f],p[h[w]]=w,p[h[f]]=f;
        }
        for(g[0]=g[t];g[0];g[0]=g[0]->u) {
            if(d[g[0]->o]>d[t]+g[0]->c) {
                d[g[0]->o]=d[t]+g[0]->c;
                if(p[g[0]->o]==N)
                    h[++k]=g[0]->o,p[h[k]]=k;
                for(w=p[g[0]->o];w>1&&d[h[w>>1]]>d[h[w]];w=f)
                    f=w>>1,h[w]^=h[f]^=h[w]^=h[f],p[h[w]]=w,p[h[f]]=f;
            }
        }
    }
    for(u=2;u<=n;u++)
        printf("%d ",d[u]==N?0:d[u]);
}