#include<fstream>
#include<vector>
#include<queue>

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 ()(var a, var b) {
        return DIST[a] > DIST[b];
    }
};

priority_queue<var, vector<var>, cmp> Q;
var n, m;
#define INF (1<<29)

bool VIZ[MAXN];
void dijkstra(var start) {

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

    DIST[start] = 0;
    Q.push(1);

    while(!Q.empty()) {
        var node = Q.top();
        Q.pop();

        if(VIZ[node]) continue;
        else VIZ[node] = 1;

        for(auto e : G[node]) {
            if(DIST[e.n] > DIST[node] + e.c) {
                DIST[e.n] = DIST[node] + e.c;
                Q.push(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++) {
        if(DIST[i] < INF)
            fout<<DIST[i]<<" ";
        else
            fout<<"0 ";
    }
}