#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#define x first
#define y second
#define pb push_back
#define NMAX 5007
using namespace std ;
vector < pair < long , long > > v [ NMAX ] ;
queue < long > q ;
pair < long , long > temp ;
bool inq [ NMAX ] ;
long dmin [ NMAX ] , n , m , nod ;
void disjkstra ( )
{
    memset ( dmin , 1000007 , sizeof ( dmin ) ) ;
    memset ( inq , 0 , sizeof ( inq ) ) ;
    q . push ( 1 ) ;
    dmin [ 1 ] = 0 ;
    inq [ 1 ] = 1 ;
    while ( ! q . empty ( ) )
    {
        nod = q . front ( ) ;
        inq [ nod ] = 0 ;
        q . pop ( ) ;
        for ( vector < pair < long , long > > :: iterator it = v [ nod ] . begin ( ) ; it != v [ nod ] . end ( ) ; ++ it )
            if ( dmin [ nod ] + it -> y < dmin [ it -> x ] )
            {
                dmin [ it -> x ] = dmin [ nod ] + it -> y ;
                if ( ! inq [ it -> x ] )
                {
                    inq [ it -> x ] = 1 ;
                    q . push ( it -> x ) ;
                }
            }
    }
}
int main ( )
{
    freopen ( "disjkstra.in" , "r" , stdin ) ;
    freopen ( "disjkstra.out" , "w" , stdout ) ;
    scanf ( "%ld %ld" , &n , & m ) ;
    for ( long i = 1 ; i <= m ; ++ i )
    {
        long a , b , c ;
        scanf ( "%ld %ld %ld" , & a , & b , & c ) ;
        temp . x = b ;
        temp . y = c ;
        v [ a ] . pb ( temp ) ;
    }
    disjkstra ( ) ;
    for ( long i = 2 ; i <= n ; ++ i )
        if ( dmin [ i ] != NMAX*NMAX )
            printf ( "%ld " , dmin [ i ] ) ;
        else
            printf ( "0 " ) ;
    return 0 ;
}