#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define NMAX 50003
#define INF 2e9

using namespace std;

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

int n, m, d[NMAX];
vector<pair<int ,int>> g[NMAX];

struct element {
    int nod, cost;
};

struct compare {
    bool operator()(element &a, element &b) {
        return a.cost > b.cost;
    }
};
priority_queue<element, vector<element>, compare> q;

void dijkstra(int sursa) {
    for (int i = 1; i <= n; i++)
        d[i] = INF;

    d[sursa] = 0;
    q.push({sursa, 0});

    element x;
    while (!q.empty()) {
        x = q.top();
        q.pop();

        if (x.cost != d[x.nod])
            continue;

        for (auto next : g[x.nod]) {
            if (d[x.nod] + next.second < d[next.first]) {
                d[next.first] = d[x.nod] + next.second;
                q.push({next.first, d[next.first]});
            }
        }
    }

}

int main() {

    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;

        g[x].push_back({y, c});
    }

    dijkstra(1);
    for (int i = 2; i <= n; i++) {
        if (d[i] == INF)
            fout << "0 ";
        else
            fout << d[i] << ' ';
    }

    return 0;
}