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

using namespace std;

const long long INF = (1LL << 60);

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

    int n, m;
    fin >> n >> m;

    // lista de adiacenta: graf[u] = vector de (v, cost)
    vector<vector<pair<int,int>>> graf(n + 1);

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        graf[a].push_back({b, c});      // graf orientat
    }

    // dist[i] = distanta minima de la 1 la i
    vector<long long> dist(n + 1, INF);
    vector<char> vizitat(n + 1, 0);

    dist[1] = 0;

    // min-heap: (distanta, nod)
    using PII = pair<long long,int>;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (!heap.empty()) {
        long long distCurenta = heap.top().first;
        int nod = heap.top().second;
        heap.pop();

        if (vizitat[nod]) continue;
        vizitat[nod] = 1;

        // daca distanta din heap nu mai este actuala, o ignoram
        if (distCurenta != dist[nod]) continue;

        for (auto &edge : graf[nod]) {
            int vecin = edge.first;
            int cost = edge.second;

            if (dist[nod] + cost < dist[vecin]) {
                dist[vecin] = dist[nod] + cost;
                heap.push({dist[vecin], vecin});
            }
        }
    }

    // afisam distantele catre 2..n
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF)
            fout << 0;
        else
            fout << dist[i];

        if (i < n) fout << ' ';
    }

    return 0;
}