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

using namespace std;
typedef int64_t var;

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

const var MAXN = 50001;
const var INF = 10000001;

struct Edge {
    var n, c;
    Edge(var a, var b) {
        n = a; c = b;
    }
};

vector<Edge> G[MAXN];
var H[MAXN], POS[MAXN], COST[MAXN], n, heapsize;


void swapp(var n1, var n2) {
    swap(H[n1], H[n2]);
    swap(POS[H[n1]], POS[H[n2]]);
}

void heap_up(var node) {
    while(node > 1 and COST[H[node/2]] > COST[H[node]]) {
        swapp(node, node/2);
        node /= 2;
    }
}

void heap_down(var node) {
    if(node*2 <= heapsize && COST[H[node*2]] <= COST[H[node]]) {
        swapp(node, node*2);
        heap_down(node*2);
    } else if(node*2+1 <= heapsize && COST[H[node*2+1]] <= COST[H[node]]) {
        swapp(node, node*2+1);
        heap_down(node*2+1);
    }
}

void update(var node) {
    heap_up(node);
    heap_down(node);
}



var extract_min() {
    swapp(1, heapsize--);
    heap_down(1);
    return H[heapsize+1];
}


bool cmp(var n1, var n2) {
    if(COST[n1] > COST[n2]) {
        swap(POS[H[n1]], POS[H[n2]]);
        return 1;
    }
    return 0;
}

void dijkstra(var start) {

    for(var i=1; i<=n; i++) {
        H[i] = i;
        POS[i] = i;
        COST[i] = INF;
    }

    COST[start] = 0;
    for(vector<Edge>::iterator it = G[start].begin(); it != G[start].end(); ++it) {
        COST[(*it).n] = (*it).c;
    }


    heapsize = n;

    make_heap(H+1, H+n+1, cmp);

    for(var i=1; i<=n; i++) {
        var node = extract_min();
        for(vector<Edge>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
            var vec = (*it).n;
            if(COST[vec] > COST[node] + (*it).c) {
                COST[vec] = COST[node] + (*it).c;
                update(POS[vec]);
            }
        }
    }
}


int main() {

    var m, a, b, c;

    fin>>n>>m;
    while(m--) {
        fin>>a>>b>>c;
        G[a].push_back(Edge(b, c));
    }

    dijkstra(1);

    for(var i=2; i<=n; i++) {
        if(COST[i] != INF) {
            fout<<COST[i]<<" ";
        } else {
            fout<<0<<" ";
        }
    }

    return 0;
}