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

#define INF (1<<15)
#define NOT_NODE -1

using namespace std;

struct Edge {
    int v, c;

    Edge(int v_, int c_) : v(v_), c(c_) { }
};

struct Heap {
    vector<int> values;
    vector<int> heap;
    vector<int> heap_node;

    Heap(int n) : values(n + 1, 0), heap_node(n + 1, NOT_NODE) {
        heap.push_back(0);
    }

    void add_value(int ind, int val) {
        values[ind] = val;

        heap.push_back(ind);
        heap_node[ind] = heap.size() - 1;

        int node = heap.size() - 1;
        while (node != 1 && values[heap[node]] < values[heap[node / 2]]) {
            swap(heap[node], heap[node / 2]);
            heap_node[heap[node]] = node;
            heap_node[heap[node / 2]] = node / 2;

            node /= 2;
        }
    }

    void remove_value(int ind) {
        if (heap_node[ind] == NOT_NODE)
            return;

        swap(heap[heap_node[ind]], heap[heap.size() - 1]);
        heap.pop_back();

        int node = heap_node[ind];
        heap_node[heap[node]] = node;

        while (node * 2 < (int)heap.size()) {
            int next = -1;
            if (node * 2 == (int)heap.size() - 1) {
                next = node * 2;
            } else {
                next = values[heap[node * 2]] < values[heap[node * 2 + 1]] ? node * 2 : node * 2 + 1;
            }

            if (values[heap[next]] < values[heap[node]]) {
                swap(heap[next], heap[node]);
                heap_node[heap[next]] = next;
                heap_node[heap[node]] = node;

                node = next;
            } else {
                break;
            }
        }

        heap_node[ind] = NOT_NODE;
    }

    void update_value(int ind, int val) {
        remove_value(ind);
        add_value(ind, val);
    }

    int min_ind() {
        return heap[1];
    }

    int min_val() {
        return values[heap[1]];
    }

    bool empty() {
        return (int)heap.size() == 1;
    }

};

int main(void) {
    int n, m;
    ifstream fin("dijkstra.in");

    fin >> n >> m;

    vector<vector<Edge> > g(n + 1, vector<Edge>());
    while (m--) {
        int v1, v2, c;
        fin >> v1 >> v2 >> c;
        g[v1].push_back(Edge(v2, c));
    }
    fin.close();

    vector<int> dist(n + 1, INF);
    dist[1] = 0;

    Heap h(n);
    for (int i = 1; i <= n; i++)
        h.add_value(i, dist[i]);

    while (!h.empty()) {
        int minn = h.min_ind();
        int minv = h.min_val();
        h.remove_value(minn);
        for (int j = 0; j < (int)g[minn].size(); j++) {
            Edge &e = g[minn][j];
            if (minv + e.c < dist[e.v]) {
                dist[e.v] = minv + e.c;
                h.update_value(e.v, dist[e.v]);
            }
        }
    }

    ofstream fout("dijkstra.out");
    for (int i = 2; i <= n; i++) {
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
    }
    fout.close();
    return 0;
}