#include <fstream>
#include <vector>
#include <set>
#define f in
#define g out
#define INF 2000000000

using namespace std;
ifstream in ( "dijkstra.in" );
ofstream out( "dijkstra.out" );
int n, m, i, j, x, y, c, nod, vecin, cost, d[50500];
vector< pair<int, int> > L[50500];
set < pair<int,int> > s;

int main() {
    
    f>>n>>m;
    for ( i=1; i <= m; i++ ){
        f>>x>>y>>c;
        L[x].push_back({y,c});
    }
    for ( i=1; i <= n; i++ )
        d[i] = INF;
    d[1] = 0;
    
    s.insert({0,1}); //d[nod], nod
    while ( !s.empty() ) {
        nod = s.begin()->second;
        s.erase(s.begin());
        for ( auto x: L[nod] ){
            vecin = x.first;
            cost = x.second;
            if ( d[vecin] > d[nod]+cost ){
                s.erase( {d[vecin], vecin} );
                d[vecin] = d[nod]+cost;
                s.insert( {d[vecin], vecin} );
            }
        }
    }
    for ( i=2; i <= n; i++ )
        if ( d[i] == INF )
            g<<"0 ";
        else g<<d[i]<<" ";
    return 0;
}