#include<stdio.h>
const unsigned short int N=50001;
struct G {
    unsigned short int o,c;
    G *u;
};
G *g[N],*r;
int m;
unsigned short int n,k,t,i,p[N],h[N],d[N],u,w,f;
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);
        r=new G;
        r->o=w,r->c=f,r->u=g[u],g[u]=r;
    }
    for(i=2;i<=n;i++)
        d[i]=p[i]=N;
    for(p[1]=h[++k]=1;k;) {
        t=h[1],u=h[1],h[1]=h[k],h[k]=u,p[h[1]]=w=1,k--;
        while(w<=k) {
            f=w;
            if((w<<1)>k)
                break;
            f=w<<1;
            if(f+1<=k&&d[h[f+1]]<d[h[f]])
                f++;
            if(d[h[w]]<=d[h[f]])
                break;
            p[h[w]]=f,p[h[f]]=w,u=h[w],h[w]=h[f],h[f]=u,w=f;
        }
        for(r=g[t];r;r=r->u) {
            if(d[r->o]>d[t]+r->c) {
                d[r->o]=d[t]+r->c;
                if(p[r->o]!=N) {
                    for(w=p[r->o];w>1;) {
                        f=w>>1;
                        if(d[h[f]]>d[h[w]])
                            p[h[w]]=f,p[h[f]]=w,u=h[f],h[f]=h[w],h[w]=u,w=f;
                        else
                            w=1;
                    }
                } else {
                    for(h[++k]=r->o,p[h[k]]=w=k;w>1;) {
                        f=w>>1;
                        if(d[h[f]]>d[h[w]])
                            p[h[w]]=f,p[h[f]]=w,u=h[f],h[f]=h[w],h[w]=u,w=f;
                        else
                            w=1;
                    }
                }
            }
        }
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]==N?0:d[i]);
}