#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define nod first
#define cost second
#define INF 2000000007

int n, m, k, i, x, y, c, SPT;
int bst[ 50050 ];
bool viz[ 50050 ];
priority_queue<pair<int, int> > myHeap;
list<pair<int, int> > myGraph[ 50050 ];
list<pair<int, int> >::iterator it;
pair<int, int> crt;

int main()
{
    fin >> n >> m;

    for ( i = 1 ; i <= n ; i++ )
        bst[ i ] = INF;

    for ( i = 1 ; i <= m ; i++ ) {
        fin >> x >> y >> c;
        myGraph[ x ].push_back( make_pair( y , c ) );
    }

    bst[ 1 ] = 0;
    myHeap.push( make_pair( 0 , 1 ) );

    while ( !myHeap.empty() ) {

        crt = myHeap.top();
        myHeap.pop();
        while ( viz[ crt.second ] ) {
            crt = myHeap.top();
            myHeap.pop();
        }
        crt.first *= -1;
        /*
        do {
            if ( myHeap.empty() )
                break;
            crt = myHeap.top();
            crt.first *= -1;
            myHeap.pop();
        } while ( viz[ crt.second ] );
        */
        if (!viz[crt.second]) {
            viz[ crt.second ] = true;

            for ( it = myGraph[ crt.second ].begin() ; it != myGraph[ crt.second ].end() ; it++ ) {
                if ( bst[ crt.second ] + it->cost < bst[ it->nod ] ) {

                    bst[ it->nod ] = bst[ crt.second ] + it->cost;
                    myHeap.push( make_pair( -( bst[ it->nod ] ) , it->nod ) );
                }
            }
        }
    }

    for ( i = 2 ; i <= n ; i++ )
        fout << bst[ i ] << ' ';


    return 0;
}