#include <fstream>
#include <vector>
#include <set>
#define nmax 250000


using namespace std;


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

set <pair <int, int> > S;
int costuri[nmax], N, M;
vector <pair <int,int>> graf[nmax];


int main()
{int a, cost, b, i;

    f>>N>>M;
    for(i = 1; i <= M; ++i){
        f>>a>>b>>cost;
        graf[a].push_back(make_pair(b, cost));
    }

    for(i = 2; i <= N; ++i)
        costuri[i] = nmax;
    costuri[1] = 0;

    S.insert( make_pair(0, 1) );

    while( !S.empty() ){

        int val = ( *S.begin() ).first, nod = ( *S.begin() ).second;

        S.erase( *S.begin() );

        for(i = 0; i < graf[nod].size(); ++i){
            if(costuri[graf[nod][i].first] > val + graf[nod][i].second){
                S.erase( make_pair(costuri[graf[nod][i].first],  graf[nod][i].first) );
                costuri[graf[nod][i].first] = val + graf[nod][i].second;
                S.insert( make_pair(costuri[graf[nod][i].first], graf[nod][i].first) );
            }
        }
    }

    for(i = 2; i <= N; ++i){
        if(costuri[i] != nmax)
            g<<costuri[i]<<' ';
        else g<<0<<' ';
    }
    g<<'\n';

    return 0;
}