#include<cstdio>
#include<list>
#define nmax 1000000000
using namespace std;
list< pair<int,int> > L[50100];
list< pair<int,int> >::iterator it;
int n,i,j,m,a,b,c,d[50100],v[50100],nmin,pmin,ok;
FILE *f,*g;
int main(){
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=2;i<=n;i++){
        v[i]=nmax;
    }
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&a,&b,&c);
        L[a].push_back(make_pair(b,c));
    }
    while(ok==0){
        nmin=nmax;
        for(i=1;i<=n;i++){
            if(d[i]==0&&nmin>v[i]){
                nmin=v[i];
                pmin=i;
            }
        }
        if(nmax==nmin){
            ok=1;
            break;
        }
        d[pmin]=1;
        for(it=L[pmin].begin();it!=L[pmin].end();it++){
            if(d[it->first]==0&&v[it->first]>v[pmin]+it->second){
                v[it->first]=v[pmin]+it->second;
            }
        }
    }
    for(i=2;i<=n;i++){
        if(v[i]==nmax)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",v[i]);
    }

    fclose(f);
    fclose(g);
    return 0;
}