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

using namespace std;

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

const int INF = 10000000000;
const int N = 50001;
const int M = 250001;
int n, m, p, x, y, nr, c, pred[N], d[N], lst[N];
int vf[2 * M], cost[2 * M], urm[2 * M];

void adauga(int x, int y, int c) {
    vf[++nr] = y;
    cost[nr] = c;
    urm[nr] = lst[x];
    lst[x] = nr;
}

priority_queue <pair <int, int>> h;

void dijkstra(int x0) {
    pair <int, int> p;
    for (int i = 1; i <= n; i++) {
        if (i == x0) d[i] = 0;
        else d[i] = INF;
    }
    h.push(make_pair(0, x0));
    while (!h.empty()) {
        p = h.top();
        h.pop();
        int x = p.second; // punem vf
        int c = -p.first; // puntem d
        if (d[x] != c) continue;
        for (int p = lst[x]; p != 0; p = urm[p]) {
            int y = vf[p];
            if (c + cost[p] < d[y]) {
                d[y] = c + cost[p];
                h.push(make_pair(-d[y], y));
            }
        }
    }
}

int main() {
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        adauga(x, y, c);
    }
    dijkstra(1);
    for (int i = 2; i <= n; i++) {
        if (d[i] != INF) out << d[i] << ' ';
        else out << -1 << ' ';
    }
    return 0;
}