#include<cstdio>
#include<vector>
#include<set>
#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,a,b,c,vmin,poz,d[50100];
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) );
    }
    d[1]=0;
    for(i=2;i<=n;i++){
        d[i]=dmax;
        s.insert( make_pair(dmax,i) );
    }
    s.insert( make_pair(0,1) );
    while(!s.empty()){
        itt=s.begin();
        vmin=itt->first;
        if(vmin==dmax)
            break;
        poz=itt->second;
        s.erase(s.begin());
        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;
}