#include <fstream>
#include <climits>
#include <vector>
#include <set>

using namespace std;

ifstream fin ( "bellmanford.in" ) ;
ofstream fout ( "bellmanford.out" ) ;

struct muchii
{
    int x ; int y ; int c ;
};

muchii muchie[250005] ;

int n , m , i , verif[50005] ;

long long int drum [250005] ;
vector <int> vect[50005] ;
vector <pair <int,int> > hp ;

void bellman_ford ( int sursa )
{
    int nod , j , poz ;

    while ( hp.size() )
    {
        nod = hp.back().second ;

        hp.pop_back() ;

        for ( j = 0 ; j < vect[nod].size() ; j ++ )
        {
            poz =  vect[nod][j] ;

            if ( drum[muchie[poz].y] > drum[muchie[poz].x] + muchie[poz].c  )
            {
                drum[muchie[poz].y] = drum[muchie[poz].x] + muchie[poz].c ;
                if ( !verif[muchie[poz].y] )
                {
                    verif[muchie[poz].y] = 1 ;
                    hp.push_back(make_pair(0,muchie[poz].y)) ;
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m ;

    for ( i = 1 ; i <= n ; i ++ )
    {
        fin >> muchie[i].x >> muchie[i].y >> muchie[i].c ;
        vect[muchie[i].x].push_back(i) ;
    }

    drum[1] = 0 ;

    for ( i = 2 ; i <= n ; i ++ )
    {
        drum[i] = INT_MAX ;
    }

    hp.push_back(make_pair(0,1)) ;

    bellman_ford ( 1 ) ;

    for ( i = 2;  i <= n ; i ++ )
    {
        fout << drum[i] << " " ;
    }

    return 0;
}