#include <vector>
#include <limits.h>
#include <fstream>

using namespace std;

const int INF = INT_MAX;

class MinHeap {
private:
    int capacity;
    vector<pair<int, int> > cost_node_pairs;
    vector<int> heap_positions;

    int father(int heap_pos);
    int left_son(int heap_pos);
    int right_son(int heap_pos);
    void up_heap(int heap_pos);
    void down_heap(int heap_pos);

public:
    MinHeap(int max_capacity);
    void insert(int node, int value);
    void remove(int heap_pos);
    void update_cost(int heap_pos, int cost);
    int get_heap_pos(int node);
    pair<int, int> top();
};

MinHeap::MinHeap(int max_capacity) {
    /* cost_node_pairs[0] and
    heap_positions[0] won't be used */
    cost_node_pairs.resize(max_capacity + 1);
    heap_positions.resize(max_capacity + 1);
    capacity = 0;
}

int MinHeap::father(int heap_pos) {
    return heap_pos / 2;
}

int MinHeap::left_son(int heap_pos) {
    return heap_pos * 2;
}

int MinHeap::right_son(int heap_pos) {
    return heap_pos * 2 + 1;
}

void MinHeap::insert(int node, int value) {
    capacity++;
    cost_node_pairs[capacity] = {value, node};
    heap_positions[node] = capacity;
    up_heap(capacity);
}

void MinHeap::remove(int heap_pos) {
    cost_node_pairs[heap_pos] = cost_node_pairs[capacity];
    heap_positions[cost_node_pairs[capacity].second] = heap_pos;
    capacity--;
    if (heap_pos > 1 && cost_node_pairs[heap_pos].first < cost_node_pairs[father(heap_pos)].first) {
        up_heap(heap_pos);
    } else {
        down_heap(heap_pos);
    }
}

void MinHeap::up_heap(int heap_pos) {
    pair<int, int> temp_pair = cost_node_pairs[heap_pos];

    int f = father(heap_pos);
    while (f > 0 && cost_node_pairs[f].first > temp_pair.first) {
        cost_node_pairs[heap_pos] = cost_node_pairs[f];
        heap_positions[cost_node_pairs[f].second] = heap_pos;
        heap_pos = f;
        f = father(heap_pos);
    }

    cost_node_pairs[heap_pos] = temp_pair;
    heap_positions[temp_pair.second] = heap_pos;
}

void MinHeap::down_heap(int heap_pos) {
    while (true) {
        int min_son = -1;
        if (left_son(heap_pos) <= capacity) {
            min_son = left_son(heap_pos);

            if (
                right_son(heap_pos) <= capacity &&
                cost_node_pairs[min_son].first > cost_node_pairs[right_son(heap_pos)].first
            ) {
                min_son = right_son(heap_pos);
            }
        }

        if (
            min_son != -1 &&
            cost_node_pairs[min_son].first < cost_node_pairs[heap_pos].first
        ) {
            swap(cost_node_pairs[min_son], cost_node_pairs[heap_pos]);
            swap(
                heap_positions[cost_node_pairs[min_son].second],
                heap_positions[cost_node_pairs[heap_pos].second]
            );
            heap_pos = min_son;
        } else {
            break;
        }
    }
}

pair<int, int> MinHeap::top() {
    return cost_node_pairs[1];
}

void MinHeap::update_cost(int heap_pos, int cost) {
    cost_node_pairs[heap_pos].first = cost;
    up_heap(heap_pos);
}

int MinHeap::get_heap_pos(int node) {
    return heap_positions[node];
}

int main() {

    // reading input

    ifstream fin("dijkstra.in");

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

    /* graph[i] = adj. list of node i + 1 */
    vector<vector<pair<int, int> > > graph(n);

    for (int i = 0; i < m; i++) {
        int node1, node2, cost;
        fin >> node1 >> node2 >> cost;
        graph[node1 - 1].push_back({cost, node2});
    }

    fin.close();


    // Dijkstra

    /* distances[i] = min cost from node 1 to node i + 1 */
    vector<int> distances(n, INF);
    distances[0] = 0;

    MinHeap min_heap(n);
    min_heap.insert(1, 0);
    for (int i = 2; i <= n; i++) {
        min_heap.insert(i, INF);
    }

    for (int i = 2; i <= n; i++) {
        pair<int, int> top = min_heap.top();
        min_heap.remove(1);

        int node = top.second - 1;
        int cost_to_node = top.first;

        for (int j = 0; j < graph[node].size(); j++) {
            int cost = graph[node][j].first;
            int neighbor = graph[node][j].second;

            if (cost_to_node != INF && cost_to_node + cost < distances[neighbor - 1]) {
                distances[neighbor - 1] = cost_to_node + cost;
                min_heap.update_cost(
                    min_heap.get_heap_pos(neighbor),
                    distances[neighbor - 1]
                );
            }
        }
    }


    // printing output

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

    return 0;
}