#include<fstream>
#include<vector>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int INF=1000000000;

struct QQ{
    int nr;
    int cost;
};

vector< pair<int,int> > a[50005];
QQ h[2*250005];
bool viz[50005];
int drum[50005],nh=0;


void urca(int pos){
    QQ t=h[pos];

    while(pos>1 && h[pos].cost < h[pos>>1].cost){
        t=h[pos];
        h[pos]=h[pos>>1];
        h[pos>>1]=t;
        pos>>=1;
    }


}

void coboara(int pos){
    int ok=pos;
    QQ t;

    while(ok){
        ok=0;
        if(pos<<1 <= nh)
            ok=pos*2;

        if(pos<<1 +1 <=nh && h[ok].cost > h[pos<<1 + 1].cost)
            ok++;

        if(h[ok].cost > h[pos].cost)
            ok=0;

        if(ok){
            t=h[ok];
            h[ok]=h[pos];
            h[pos]=t;
            pos=ok;
        }
    }
}


void insera(int x, int y){
    nh++;
    h[nh].nr=x;
    h[nh].cost=y;

    urca(nh);

}

void sterge(int pos){
    h[pos]=h[nh];
    nh--;

    if(pos>1 && h[pos].cost < h[pos>>1].cost)
        urca(pos);
    else
        coboara(pos);

}





int main(){
    int n,m,i,j,x,y,z;

    f>>n>>m;

    QQ q;
    for(i=1; i<=m; ++i){
        f>>x>>y>>z;
        a[x].push_back(make_pair(y,z));

    }

   // f>>s>>e;

    for(i=1; i<=n; ++i){
        drum[i]=INF;
    }

    drum[1]=0;

    insera(1,0);


    int v,t,l;
    while(nh>0){
        v=h[1].nr;

        viz[v]=1;

        sterge(1);

        for(i=0; i<a[v].size(); ++i){
            t=a[v][i].first;
            l=a[v][i].second;

            if(drum[t] > drum[v]+l){
                drum[t]=drum[v]+l;

                insera(t,drum[t]);
            }
        }
    }


   for(i=2; i<= n; ++i)
        if(drum[i]==INF)
            g<<"0 ";
        else
            g<<drum[i]<<' ';




return 0;
}