#include<cstdio>
#include<iostream>
#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, itt1;
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(nmax,i));
        d[i]=nmax;
    }
    s.insert(make_pair(0,1));
    d[1]=0;
    while(ok==0 && !s.empty()){
        itt=s.begin();
        val=itt->first;
        nod=itt->second;
        if(nmax==val){
            ok=0;
            break;
        }
        /*for (itt1 = s.begin(); itt1!= s.end(); itt1++) {
            cout<<itt1->first<<" "<<itt1->second<<"\n";
        }
*/
        s.erase(itt);

  /*      cout<<"*\n";

        for (itt1 = s.begin(); itt1!= s.end(); itt1++) {
            cout<<itt1->first<<" "<<itt1->second<<"\n";
        }

*/
        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(d[it->first],it->first));
                s.erase(itt);
                d[it->first]=d[nod]+it->second;
                s.insert(   make_pair(d[it->first],it->first)  );
            }
        }

        /*cout<<"*\n";
        for (itt1 = s.begin(); itt1!= s.end(); itt1++) {
            cout<<itt1->first<<" "<<itt1->second<<"\n";
        }
        */
        i++;
    }
    for(i=2;i<=n;i++){
        if(d[i]==nmax)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",d[i]);
    }

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