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

using namespace std;

typedef pair<int, int> Edge;

vector<int> heap;
vector<int> dist;
vector<int> heap_pos;

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

        if (dist[heap[next]] < dist[heap[node]]) {
            swap(heap[next], heap[node]);
            heap_pos[heap[next]] = next;
            heap_pos[heap[node]] = node;

            node = next;
        } else {
            break;
        }
    }
}

void up_heap(int node) {
    while (node != 1) {
        if (dist[heap[node]] < dist[heap[node / 2]]) {
            swap(heap[node], heap[node / 2]);
            heap_pos[heap[node]] = node;
            heap_pos[heap[node / 2]] = node / 2;
            node = node / 2;
        } else {
            break;
        }
    }
}

void insert_heap(int graph_node)
{
    heap.push_back(graph_node);
    heap_pos[graph_node] = heap.size() - 1;

    int node = heap.size() - 1;
    up_heap(node);
}

void remove_heap(int graph_node) {
    swap(heap[heap_pos[graph_node]], heap[heap.size() - 1]);
    heap.pop_back();

    int node = heap_pos[graph_node];
    heap_pos[heap[node]] = node;

    down_heap(node);
}

void update_heap(int graph_node) {
    int node = heap_pos[graph_node];
    up_heap(node);
    down_heap(node);
}

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

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

    vector<vector<Edge> > g(n, vector<Edge>());

    for (int i = 0; i < m; i++) {
        int e1, e2, cost;
        fin >> e1 >> e2 >> cost;
        --e1;
        --e2;
        g[e1].push_back(make_pair(e2, cost));
        g[e2].push_back(make_pair(e1, cost));
    }

    dist = vector<int>(n, 1 << 15);
    heap_pos = vector<int>(n, -1);

    vector<bool> in_heap(n, true);

    dist[0] = 0;
    heap.push_back(0);

    for (int i = 0; i < n; i++) {
        insert_heap(i);
    }

    for (int i = 0; i < n; i++) {
        int minn = heap[1];
        int minv = dist[heap[1]];

        remove_heap(minn);
        in_heap[minn] = false;

        for (vector<Edge>::iterator it = g[minn].begin(); it < g[minn].end(); it++) {
            if(minv + (*it).second < dist[(*it).first]) {
                dist[(*it).first] = minv + (*it).second;
                if (in_heap[(*it).first]) {
                    remove_heap((*it).first);
                    insert_heap((*it).first);
                }
            }
        }
    }

    ofstream fout("dijkstra.out");
    for (int i = 1; i < n; i++)
        fout << dist[i] << " ";
    return 0;
}