#include<fstream>
#include<vector>
#include<set>

using namespace std;
typedef int var;

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

#define MAXN 50001
#define INF (1<<30)


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


var DIST[MAXN];
vector<Edge> G[MAXN];
var n;

struct cmp {
    const bool operator () (const var &a, const var &b) const {
        return DIST[a] < DIST[b];
    }
};
set<var, cmp> SET;

void dijkstra(var start) {
    for(var i=1; i<=n; i++) {
        DIST[i] = INF;
    }
    DIST[start] = 0;
    SET.insert(start);

    while(!SET.empty()) {
        var node = *(SET.begin());
        SET.erase(SET.begin());

        for(vector<Edge>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
            Edge &e = *it;
            if(DIST[e.n] > DIST[node] + e.c) {
                DIST[e.n] = DIST[node] + e.c;
                set<var>::iterator itt = SET.find(e.n);
                if(itt != SET.end()) {
                    SET.erase(itt);
                }
                SET.insert(e.n);
            }
        }
    }
}

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++) {
        fout<<DIST[i]<<" ";
    }
}