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

using namespace std;
typedef int var;

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

#define MAXN 100003
var DIST[MAXN];

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

vector<Edge> G[MAXN];

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

multiset<var,cmp> SET;
var n, m;
#define INF (1<<25)

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

    while(!SET.empty()) {
        var node = *(SET.begin());
        SET.erase(SET.begin());
        multiset<var>::iterator it;
        for(auto e : G[node]) {
            if(DIST[e.n] > DIST[node] + e.c) {
                DIST[e.n] = DIST[node] + e.c;
                it = SET.find(e.n);
                if(it != SET.end())
                    SET.erase(it);
                SET.insert(e.n);
            }
        }
    }

}


int main() {
    var 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]<<" ";
    }
}