#include <algorithm>
#include <climits>
#include <fstream>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

#define MAXN 50001

long long d[MAXN];

vector<pair<int, long long>> g[MAXN];

int n, m;

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

    fin >> n >> m;
    int x, y, w;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> w;
        g[x].push_back(make_pair(y, w));
    }

    for (int i = 2; i <= n; i++) {
        d[i] = LONG_MAX;
    }
    d[1] = 0;

    set<pair<long long, int>> h;
    h.insert(make_pair(0, 1));

    while (h.size() > 0) {
        int x = h.begin()->second;
        long long val = h.begin()->first;
        h.erase(h.begin());
        for (const pair<int, long long> &p : g[x]) {
            if (d[p.first] > p.second + val) {
                d[p.first] = p.second + val;
                h.insert(make_pair(d[p.first], p.first));
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        fout << d[i] << ' ';
    }
    fout << '\n';

    fin.close();
    fout.close();

    return 0;
}