#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
using namespace std ;
const int NR =  50005 , oo = ( 1 << 30 ) ;
ifstream in ("dijkstra.in") ;
ofstream out ("dijkstra.out") ;
int n , m , x , y , c ;
vector < pair < int , int > > v [ NR ] ;
vector < int > d ( NR , oo ) ;
struct cmp  {
inline bool operator() ( const int i , const int j )    {
return d [ i ] > d [ j ] ;
}
};
bitset < NR > inq ;
priority_queue <  int  , vector < int > , cmp > q ;
static void dijkstra ( )  {
    int nod , cost ;
    d [ 1 ] = 0 ;
    q.push( 1 ) ;
    while ( !q.empty() )    {
        nod = q.top() ;
        q.pop() ;
        inq [ nod ] = 0 ;
        for ( vector < pair < int , int > > :: iterator it = v [ nod ].begin() ; it < v [ nod ].end() ; ++ it ) {
            if ( d [ nod ] + (*it).s < d [ (*it).f ] )  {
                d [ (*it).f ] = d [ nod ] + (*it).s ;
                 if ( !inq [ (*it).f ] )
                 q.push( (*it).f ) ,
                 inq [ (*it).f ] = 1 ;
            }
        }
    }
    for ( nod = 2 ; nod <= n ; ++ nod )
        if ( d [ nod ] == oo )  out << "0 " ;
        else                    out << d [ nod ] << ' ' ;
}
int main () {
    in >> n >> m ;
    while ( m -- )  {
        in >> x >> y >> c ;
        v [ x ].pb ( { y , c } ) ;
    }
    dijkstra ( ) ;
}