#include <fstream>
#include <vector>
#include <queue>
#define inf 99999
#define pp pair <int, int>

using namespace std;

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

/*struct edge {
    pair <int, int> vert;
    int cost;
    edge (pair <int, int> v, int c): vert(v), cost(c) {};
};*/

vector <pp> v[50000];
priority_queue <pp, vector<pp>, greater<pp> > Q;

int n, m, x, y, w, d[50002], s;

int main () {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> w;
        v[x].push_back(pp(w, y));
    }
    for (int i = 1; i <= n; i++) {
        d[i] = inf;
    }

    s = 1;
    d[s] = 0;
    Q.push(pp(d[s], s));
    while (!Q.empty()) {
        x = Q.top().second;
        Q.pop();
        int size = v[x].size();
        for (int i = 0; i < size; i++) {
            y = v[x][i].second;
            w = v[x][i].first;
            if (d[y] > d[x] + w) {
                d[y] = d[x] + w;
                Q.push(pp(d[y], y));
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (d[i] == inf)
            fout << 0 << " ";
        else
            fout << d[i] << " ";
    }
}