#include<stdio.h>
int m,i,o,n,d[50001],a[250000],b[250000],c[250000];
int main() {
    freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%d%d%d",a+i,b+i,c+i);
    for(i=2;i<=n;i++)
        d[i]=50001;
    while(!o) {
        for(o=1,i=0;i<m;i++)
            if(d[b[i]]>d[a[i]]+c[i])
                o=0,d[b[i]]=d[a[i]]+c[i];
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]==50001?0:d[i]);
}