#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 50000;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct edge {
    int y;
    int cost;
}; vector <edge> g[NMAX + 1];

// Min_heap with costs (we store nodes in heap)
int heap[NMAX + 1], heap_size;
// Min distance to reach each node
int dist[NMAX + 1];
// Position in heap for each node
int pos_heap[NMAX + 1];
// Marks discovered nodes by dijkstra
bool found[NMAX + 1];

void heapSwap(int pos_a, int pos_b) {
    swap(pos_heap[heap[pos_a]], pos_heap[heap[pos_b]]);
    swap(heap[pos_a], heap[pos_b]);
}

void heapUp(int pos) {
    int father = (pos >> 1);

    while (pos > 1 && dist[heap[pos]] < dist[heap[father]]) {
        heapSwap(pos, father);
        pos = father;
        father = (pos >> 1);
    }
}

void heapDown(int pos) {
    int left_son = (pos << 1);
    int right_son = left_son + 1;
    int best;

    while (left_son <= heap_size) {
        best = left_son;
        if (right_son <= heap_size && dist[heap[left_son]] > dist[heap[right_son]])
            best = right_son;

        if (dist[heap[pos]] <= dist[heap[best]])
            break;

        heapSwap(pos, best);
        pos = best;
        left_son = (pos << 1);
        right_son = left_son + 1;
    }
}

void heapInsert(int node) {
    ++heap_size;
    heap[heap_size] = node;
    pos_heap[node] = heap_size;
    
    heapUp(heap_size);
}

void heapErase(int node) {
    int pos = pos_heap[node];
    heapSwap(pos, heap_size);
    --heap_size;

    heapDown(pos);
    // heapUp(pos);
}

void heapUpdate(int node) {
    int pos = pos_heap[node];
    heapUp(pos);
    // heapDown(pos);
}

void dijkstra(int source) {
    int x, y, cost;
    found[source] = true;
    dist[source] = 0;
    heapInsert(source);

    while (heap_size > 0) {
        x = heap[1];
        heapErase(x);

        for (int i = 0; i < g[x].size(); ++i) {
            y = g[x][i].y;
            cost = g[x][i].cost;

            if (!found[y]) {
                found[y] = true;
                dist[y] = dist[x] + cost;
                heapInsert(y);
            } else if (dist[x] + cost < dist[y]) {
                dist[y] = dist[x] + cost;
                heapUpdate(y);
            }
        }
    }
}

int main() {
    int n, m, x;
    edge aux;

    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> aux.y >> aux.cost;
        g[x].push_back(aux);
    }

    dijkstra(1);

    for (int i = 2; i <= n; ++i) {
        fout << dist[i] << " ";
    }
    fout << "\n";

    return 0;
}