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

using namespace std;

struct Item { //Item struktura (a, b csucspontok. g suly)
    int p;
    int g;

    Item(int w, int r) { //constructor
        p = w;
        g = r;
    }
};

struct Compare { //priority_queue osszehasonlitas
    bool operator()(Item &i1, Item &i2) {
        return i1.g > i2.g;
    }
};

const int INF = numeric_limits<int>::max() / 2;
int n;

priority_queue<Item, vector<Item>, Compare> prq;
vector<Item> *graph;

void beolvas() {
    int m, u, v, k;
    ifstream input("dijkstra.in");
    input >> n >> m;

    graph = new vector<Item>[n + 1];

    for (int i = 0; i < m; i++) {
        input >> u >> v >> k;
        graph[u].push_back(Item(v, k));
        graph[v].push_back(Item(u, k));
    }

    input.close();
}

void dijkstra(int r) {
    int d[n + 1];
    bool used[n + 1];

    for (int i = 1; i <= n; i++) {
        d[i] = INF;
        used[i] = false;
    }

    d[r] = 0;
    prq.push(Item(r, 0));

    Item u = Item(0, 0), v = Item(0, 0);
    while (prq.size() > 0) {
        int ujtav = 0;
        u = prq.top();
        prq.pop();

        if (used[u.p]) continue;
        used[u.p] = true;

        for (int i = 0; i < graph[u.p].size(); i++) {
            v = graph[u.p][i];
            ujtav = d[u.p] + v.g;

            if (!used[v.p] && ujtav < d[v.p]) {
                d[v.p] = ujtav;
                prq.push(Item(v.p, ujtav));
            }
        }
    }

    ofstream out("dijkstra.out");
    for (int i = 2; i <= n; i++) {
        out << d[i] << " ";
    }
    out << endl;
}

int main() {
    beolvas();
    dijkstra(1);

    return 0;
}