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

using namespace std;

struct Item {
    int p;
    int g;
    Item(int a, int b) {
        p = a;
        g = b;
    }
};

struct Compare {
    bool operator()(Item &e1, Item &e2) const {
        return e2.g < e1.g;
    }
};

const int INF = numeric_limits<int>::max() / 2;
int n;
vector<Item> *graph;
priority_queue<Item, vector<Item>, Compare> prq;
int *parent, *d;

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

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

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

    input.close();
}

void Dijkstra(int r) {
    int ujtav = 0;
    bool used[n + 1];
    for (int i = 1; i <= n; i++) {
        used[i] = false;
        d[i] = INF;
        parent[i] = 0;
    }

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

    Item u = Item(0, 0), v = Item(0, 0);
    while (prq.size() > 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;
                parent[v.p] = u.p;
                prq.push(Item(v.p, ujtav));
            }
        }
    }
}

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

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

    return 0;
}