#include <fstream>
#include <queue>
#include <vector>

#define IN "dijkstra.in"
#define OUT "dijkstra.out"

#define f first
#define s second
#define mp make_pair

#define pu push
#define p pop

const int MAX = 50014 ;
const int inf = 1 << 30 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

int n , m , d [ MAX ] ;

typedef pair < int , int > P ;

vector < P > gr [ MAX ] ;

struct cmp {
    bool operator () ( const P &a , const P &b ){
        return ( a.s > b.s ) ;
    }
};

priority_queue < P , vector < P > , cmp > heap ;

void dijkstra ( int nod ) ;

int main()
{
    fin >> n >> m ;
    for ( register int i = 1 ; i <= m ; ++ i ){
        int x , y , z ;
        fin >> x >> y >> z ;
        gr [ x ].push_back ( mp ( y , z ) ) ;
    }
    for ( register int i = 2 ; i <= n ; ++ i )
        d [ i ] = inf ;
    dijkstra ( 1 ) ;
    for ( register int  i = 2 ; i <= n ; ++ i )
        if ( d [ i ] != inf )
            fout << d [ i ] << " " ;
        else
            fout << "0 " ;
    return 0;
}

void dijkstra ( int nod ) {
    heap.pu ( mp ( 1 , 0 ) ) ;
    d [ 1 ] = 0 ;
    while ( !heap.empty () ){
        int nod = heap.top ().f ;
        int cost = heap.top ().s ;
        heap.p ( ) ;
        if ( d [ nod ] != cost ) continue ;
        for ( auto x : gr [ nod ] )
            if ( x.s + cost < d [ x.f ] ){
                d [ x.f ] = x.s + cost ;
                heap.pu ( mp ( x.f , d [ x.f ] ) ) ;
            }
    }
}