#include <vector>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <queue>
 
#define MAX_SIZE 50005
#define get_max( a,b) ((a)>(b)?(a):(b))
#define mk make_pair
#define INF 0x3f3f3f3f
 
using namespace std;
 
typedef vector < pair < int,int > > ::iterator vii;
 
ifstream in ( "dijkstra.in" );
ofstream out ( "dijkstra.out" );
 
vector <  pair < int  ,int > > G[MAX_SIZE] ;
int N , M , Cost[MAX_SIZE] ;
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > Heap;
 
void Dijkstra ( void )
{
    memset ( Cost , INF , sizeof ( Cost ) );
    Cost[1] = 0 ;
    Heap.push(mk( 0 , 1));
    for ( ; !Heap.empty() ; )
    {
        int node = Heap.top().second , val = Heap.top().first;
        Heap.pop();
        for( vii it = G[node].begin();  it != G[node].end() ; ++it )
            if ( Cost[it->first] > val + it->second )
            {
                Cost[it->first] = val + it->second;
                Heap.push(mk( Cost[it->first],it->first  ));
            }
    }
}
 
 
int main ( void )
{
    int i , j , x , y , c ;
    in >> N >> M ;
    for ( i = 1 ; i <= M ; ++i )
    {
        in >> x >> y >> c ;
        G[x].push_back(mk(y,c));
    }
    Dijkstra();
    for ( i = 2 ; i <= N ; ++i )
        out << ( Cost[i] == INF ? 0 : Cost[i] ) << " ";
    in.close();
    out.close();
    return 0 ;
}