#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

FILE *f = fopen ( "dijkstra.in" , "r" ) , *g = fopen ( "dijkstra.out" , "w" );

struct type_pair {
    int first , second;
};

const int MAX = 50005 , INF = 2000000000;
int N , M , i , x , y , cost , dist [ MAX ] , vertex , edge_cost , node;
type_pair aux , object;
vector < type_pair > edge [ MAX ];
bool update;

struct mycmp {
    bool operator() ( const type_pair a , const type_pair b )
    {
        return dist [ edge [ a . first ] [ a . second ] . first ]  > dist [ edge [ b . first ] [ b . second ] . first ];
    }
};

priority_queue < type_pair , vector < type_pair > , mycmp > minim;

void read()
{
    fscanf ( f , "%d %d" , &N , &M );
    object.first = 1 , object.second = 0;
    edge [ 1 ] . push_back ( object ); //edge going from 1 to 1 with cost 0
    for ( i = 1 ; i <= M ; i ++ )
    {
        fscanf ( f , "%d %d %d" , &x , &y , &cost );
        object.first = y , object.second = cost;
        edge [ x ] . push_back ( object );
    }
}

void get ( int &node )
{
    aux = minim . top ();
    minim . pop ();
    node = edge [ aux . first ] [ aux . second ] . first;
}

bool apply_updates ( int node )
{
    bool update = false;
    for ( i = 0 ; i < edge [ node ] . size() ; i ++ )
    {
        vertex = edge [ node ] [ i ] . first;
        edge_cost = edge [ node ] [ i ] . second;
        if ( dist [ vertex ] > dist [ node ] + edge_cost )
        {
            update = true;
            dist [ vertex ] = dist [ node ] + edge_cost;
            object.first = node , object.second = i;
            minim . push ( object );
        }
    }
    return update;
}

void dijkstra()
{
    //set cost of reaching i to INF apart from 1 which is 0
    for ( i = 1 ; i <= N ; dist [ i ] = INF , i ++ );
    dist [ 1 ] = 0;
    //push in the queue
    object.first = 1 , object.second = 0;
    minim.push ( object );

    do {
        update = false; //can we update more?
        get ( node ); // obtain the node that could get to other nodes with the lowest cost
        update = apply_updates( node ); // search for possible new paths
    } while ( !minim.empty() );
}

void print()
{
    for ( i = 2 ; i <= N ; i ++ )
        fprintf ( g , "%d " , dist [ i ] );
}

int main()
{
    read();
    dijkstra();
    print();
    return 0;
}