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

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