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

using namespace std;

#define inFile "dijkstra.in"
#define outFile "dijkstra.out"
#define MAX_VERT 50001
#define INF 1<<30

int h_el;
int d[MAX_VERT];
int pos[MAX_VERT];
int h[MAX_VERT];

struct edge {
    int node;
    int cost;
};
vector < edge > v[MAX_VERT];

void upHeap(int x) {
    int init = h[x];
    while(x > 1 && d[init] < d[h[x/2]]) {
        pos[h[x/2]] = x;
        h[x] = h[x/2];
        x /= 2;
    }
    pos[init] = x;
    h[x] = init;
}

void downHeap(int x) {
    int son;
    do {
        son = 0;
        if(2*x <= h_el) son = 2*x;
        if(2*x+1 <= h_el && d[h[2*x+1]] < d[h[son]]) son = 2*x+1;
        if(d[h[son]] > d[h[x]]) son = 0;
        if(son) {
            pos[h[son]] = x;
            pos[h[x]] = son;
            swap(h[x], h[son]);
            x = son;
        }
    } while(son);
}

void addHeap(int key) {
    h[++h_el] = key;
    pos[key] = h_el;
    upHeap(h_el);
}

void remHeap(int key) {
    pos[h[key]] = -1;
    h[key] = h[h_el--];
    if(key > 1 && d[h[key]] < d[h[key/2]]) upHeap(key);
    else downHeap(key);
}

int main() {
    ifstream in(inFile);
    ofstream out(outFile);

    int n, m, x, y, dist, i;
    
    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> x >> y >> dist;
        v[x].push_back({y,dist});
    }
    
    h_el = n;
    for(i = 1; i <= n; i++) {
        d[i] = INF;
        pos[i] = i;
        h[i] = i;
    }
    d[1] = 0;
    
    int node, nextNode, altDist;
    
    while(h_el) {
        node = h[1];
        for(i = 0; i < v[node].size(); i++) {
            nextNode = v[node][i].node;
            if(pos[nextNode] == -1) continue;
            altDist = d[node] + v[node][i].cost;
            if(altDist < d[nextNode]) {
                d[nextNode] = altDist;
                upHeap(pos[nextNode]);
            }
        }
        remHeap(1);
    }
    
    for(i = 2; i <= n; i++)
        out << d[i] << ' ';
    out << '\n';
    
    return 0;
}