#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

using namespace std ;

const int NMAX = 50001 ;
const int INF = 0x3f3f3f3f ;

struct NOD {
int x, y;};

inline void Dijkstra() ;

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

int A, B, C, N, M, cost, aux, nod_act;
vector < NOD > a[NMAX] ;
vector < int > d(NMAX, INF) ;
queue < int > Q ;

inline void Dijkstra() {

Q.push(1) ;
d[1] = 0 ;

while(!Q.empty()) {

    aux = Q.front() ;
    Q.pop() ;

    for(unsigned int i = 0 ; i < a[aux].size() ; ++ i)
    {

        cost = a[aux][i].y ;
        nod_act = a[aux][i].x ;

        if(d[nod_act] > d[aux] + cost)
        {
            d[nod_act] = d[aux] + cost ;
            Q.push(nod_act) ;
        }
    }
}

}

int main()
{

    NOD aux1 ;

    ///Citire
    cin >> N >> M ;

    for(int i = 1 ; i <= M ; ++ i)
    {

        cin >> A >> B >> C ;


        aux1.x = B ; //Retinem directia.
        aux1.y = C ; //Directia.
        a[A].push_back(aux1) ; //introducem intr-o coada.
    }

    Dijkstra() ;


    ///Afisare

    for(int i = 1 ; i < N ; ++ i)
    {
        if(d[i +1] != INF)
            cout << d[i + 1] << ' ' ;
        else cout << 0 << ' ' ;
    }
    cout << '\n' ;

    cin.close() ;
    cout.close() ;
}