#include<cstdio>
#include<set>
#include<vector>
#define dmax 2000000000
using namespace std;
vector< pair<int,int> >L[50100];
vector< pair<int,int> >::iterator it;
set< pair<int,int> >s;
set< pair<int,int> >::iterator itt;
int n,m,i,j,d[50100],v[50100],a,b,c,ok,vmin,poz;
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;i++){
        d[i]=dmax;
        s.insert(make_pair(dmax,i));
    }
    d[1]=0;
    s.insert(make_pair(0,1));
    while(!ok&&!s.empty()){
        itt=s.begin();
        vmin=itt->first;
        if(vmin==dmax)
            break;
        poz=itt->second;
        v[poz]=1;
        s.erase(itt);
        for(it=L[poz].begin();it!=L[poz].end();it++){
            if(d[it->first]>d[poz]+it->second){
                s.erase(s.find(make_pair(d[it->first],it->first)));
                d[it->first]=d[poz]+it->second;
                s.insert(make_pair(d[it->first],it->first));
            }
        }
    }
    for(i=2;i<=n;i++){
        if(d[i]==dmax)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",d[i]);
    }



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