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

using namespace std;

ifstream in("dijkstra.in") ;
ofstream out("dijkstra.out") ;

const int N = 50001 ;
const int INF = 1e9 + 15 ;

vector <pair <int , int>> a[N] ;
priority_queue <pair <int , int>> pq;
bitset <N> prelucrat ;
int d[N] , n , m ;

int main()
{
    in >> n >> m ;
    for ( int i = 0 ; i < m ; i++ )
    {
        int x , y , c ;
        in >> x >> y >> c ;
        a[x].push_back( {y , c} ) ;
    }
    for ( int i = 2 ; i <= n ; i++ )
    {
        d[i] = INF ;
    }
    d[1] = 0 ;
    pq.push ( { 0 , 1 } ) ;
    while ( !pq.empty () )
    {
        int x = pq.top().second ;
        pq.pop() ;
        if ( prelucrat [x] ) continue ;
        prelucrat [x] = 1 ;
        for ( auto p: a[x] )
        {
            int y = p.first ;
            int c = p.second ;
            if ( d[x] + c < d[y] )
            {
                d[y] = d[x] + c;
                pq.push ( { -d[y] , y } ) ;
            }
        }
    }
    for ( int i = 2 ; i <= n ; i++ )
    {
        if ( d[i] == INF )
        {
            d[i] = 0;
        }
        out << d[i] << " ";
    }
    out.close();
    return 0;
}