#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
using namespace std;

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

vector<pair<int, int> > v[50005];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > qp;
int n, m, val, a, b, p, s, cnt, valmin = 1e9, valmax = 0, d[50005], f[50005], xs, xd;

int main() {
    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        fin >> a >> b >> val;
        v[a].push_back({b, val});
    }
    s=1;
    fill(d + 1, d + n + 1, 1e9);
    d[s] = 0;
    qp.push({0, s});

    while (!qp.empty()) {
        xs = qp.top().second;
        xd = qp.top().first;
        qp.pop();

        if (f[xs] == 1) {
            continue;
        }

        f[xs] = 1;
        d[xs] = xd;

        for (int i = 0; i < v[xs].size(); i++) {
            if (f[v[xs][i].first] == 0) {
                if (d[v[xs][i].first] > xd + v[xs][i].second) {
                    d[v[xs][i].first] = xd + v[xs][i].second;
                    qp.push({d[v[xs][i].first], v[xs][i].first});
                }
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (d[i] != 1e9) {
            fout << d[i] << " ";
        } else {
            fout << 0 << " ";
        }
    }
    fin.close();
    fout.close();
    return 0;
}