#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>

using namespace std ;

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

const int NR = 50005 ;
const int oo = ( 1 << 30 ) ;

vector < int > d ( NR , oo ) ;
vector < pair < int , int > > v [ NR ] ;
bool M [ NR ] ;

struct cmp{

    bool operator () ( int x , int y )
    {
        return d [ x ] > d [ y ] ;
    }
};

priority_queue < int , vector < int > , cmp > coada ;

int n , m ;

void citirea ( )
{
    f >> n >> m ;
    for ( int i = 1 ; i <= m ; ++ i )
    {
        int a , b , c ; f >> a >> b >> c ;
        v [ a ]. push_back ( make_pair ( b , c ) ) ;
    }
}

void afisare ( )
{
    for ( int i = 2 ; i <= n ; ++ i )
    if ( d [ i ] == oo )    g << "0 " ;
    else                    g << d [ i ] << " " ;
}

void dijkstra ( int start )
{
    d [ start ] = 0 ;
    coada.push( start ) ;
    M [ start ] = true ;
    while ( !coada.empty() )
    {
        int nod = coada.top() ;
        coada.pop();
        M [ nod ] = false ;
        for ( size_t i = 0 ; i < v [ nod ].size() ; ++ i )
        {
            int cost = v [ nod ][ i ].second ;
            int vecin = v [ nod ][ i ].first ;
            if ( d [ nod ] + cost < d [ vecin ] )
            {
                d [ vecin ] = d [ nod ] + cost ;
                if ( !M [ vecin ] )
                    coada.push(vecin) ; M [ vecin ]= true ;
            }

        }
    }
}

int main ()
{
    citirea ( ) ;
    dijkstra( 1 ) ;
    afisare ( ) ;
}