#include<fstream>
#include<set>
#include<vector>
#define dim 50007
#define inf 20000000
using namespace std;

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

vector< pair< int ,int  > > G[dim];
set< pair < int ,int  > > h;
int n,m,i,j,x,y,c;
int d[dim];

int main () {

    f>>n>>m;

    for(i=1;i<=m;++i){

        f>>x>>y>>c;
        G[x].push_back( make_pair (y,c));

    }
    for(i=2;i<=n;++i){
        d[i]=inf;
    }
    h.insert(make_pair(0,1));

    while(h.size() >0 ) {

        c=(*h.begin()).first;
        x=(*h.begin()).second;
        h.erase(*h.begin());
        for(i=0;i<G[x].size();++i ) {

            if(d[G[x][i].first]>c+G[x][i].second) {
                d[G[x][i].first]=c+G[x][i].second;
                h.insert(make_pair(d[G[x][i].first],G[x][i].first));
            }

        }
    }
    for(i=2;i<=n;++i){

        if(d[i]==inf){
            g<<0<<" ";
        }
        else
            g<<d[i]<<" ";
    }
    return 0;
}