#include <iostream>
#include <fstream>
#include <set>
#include <queue>
#define INF 0xffffff

using namespace std;

set <pair <int, int> > mat[50001]; /// x->y with c: mat[x] = [<y, c>]
set <pair <int, pair <int, int> > > q;/// x->y with c: <c, <x, y> >
int cost [50001];

int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    int n, m, x, y, c, i;
    set <pair <int, int> > ::iterator k;
    pair <int, pair <int, int> > now;
    in >> n >> m;
    for (i = 2; i <= n; ++i) {cost[i] = INF;}
    for (i = 0; i < m; ++i) {
        in >> x >> y >> c;
        mat[x].insert(make_pair(y, c));
    }

    for (k = mat[1].begin(); k != mat[1].end(); ++k) {q.insert (make_pair (k->second, make_pair (1, k->first)));}

    while (!q.empty()) {
        now = *q.begin();
        x = now.second.first;
        y = now.second.second;
        c = now.first;

        if (cost[y] > cost[x] + c) {
            cost[y] = cost[x] + c;
            for (k = mat[y].begin(); k != mat[y].end(); ++k) {q.insert (make_pair (k->second, make_pair (y, k->first)));}
        }

        q.erase (now);
    }

    for (i = 2; i <= n; ++i) {out << ((cost[i] == INF) ? 0 : cost[i]) << " ";}

    return 0;
}