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

using namespace std;

vector <vector <pair <int, int> > > mat;
vector <int> cost;
priority_queue <pair <int, pair <int, int> > > q;/// x->y with c: <c, <x, y> >

int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    int n, m, x, y, c, i;
    in >> n >> m;
    cost.resize (n+1, INF);cost[1] = 0;
    mat.resize (n+1);

    for (i = 0; i < m; ++i) {
        in >> x >> y >> c;
        mat[x].push_back (make_pair(y, c));
    }
    vector <pair <int, int> > ::iterator k;
    for (k = mat[1].begin(); k != mat[1].end(); ++k) {q.push (make_pair (-k->second, make_pair(1, k->first)));}

    pair <int, pair <int, int> > now;
    while (!q.empty()) {
        now = q.top();
        q.pop();
        c = -now.first;
        x = now.second.first;
        y = now.second.second;

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

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

    return 0;
}