#include <fstream>
#include <vector>
#include <iostream>
#include <set>
#include <utility>

using std::set;
using std::vector;
using std::endl;
using std::cout;
using std::pair;
using std::make_pair;

const int INF = 0x3f3f3f;

struct muchie
{
    int nod2;
    int dist;
};


vector< vector<muchie> > a;
vector< pair<int, int> > DIST;

int VSD()
{
    int dist = INF;
    int n;
    for (int i = 1; i < DIST.size(); ++i)
        if ( DIST[i].first < dist && DIST[i].second == 0 ) {
        dist = DIST[i].first;
        n = i;
        }
    return n;
}

int main()
{
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");
    int N,M;
    in >> N >> M;
    ++N;
    a.resize(N);
    for (int i = 0; i < M; ++i)
    {
        muchie temp;
        int x;
        in >> x >> temp.nod2 >> temp.dist;
        a[x].push_back(temp);
    }

    DIST.resize(N);
    DIST[0] = make_pair(INF, N - 1);
    DIST[1] = make_pair(0, 0);
    for (int i = 2; i < N; ++i)
        DIST[i] = make_pair(INF, 0);



    while ( DIST[0].second > 0 )
    {

        int tnode = VSD();
        DIST[tnode].second = 1;
        DIST[0].second--;
        if ( DIST[tnode].first == INF ) break;

        for (int i = 0; i < a[tnode].size(); ++i)
            if ( DIST[ a[tnode][i].nod2 ].second == 0 &&
                 DIST[tnode].first + a[tnode][i].dist < DIST[ a[tnode][i].nod2 ].first )
                 DIST [ a[tnode][i].nod2 ].first =  DIST[tnode].first + a[tnode][i].dist;

    }

    for (int i = 2; i < DIST.size(); ++i)
        out << DIST[i].first << " ";


    return 0;
}