#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 ) ;
queue < int > q ;
bitset < NR > inq ;
void dijkstra ( )  {
    // de fapt bellman
    int nod ;
    d [ 1 ] = 0 ;
    q.push( 1 ) ;
    inq [ nod ] = 0 ;
    while ( !q.empty() )    {
        nod = q.front() ;
        q.pop() ;
        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 ( ) ;
}