#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 <pair <int, int> > v[50000];
priority_queue <pair <int, int> > Q;

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

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

    s = 1;
    d[s] = 0;
    Q.push(make_pair(d[s], s));
    while (!Q.empty()) {
        x = Q.top().second;
        Q.pop();
        int size = v[x].size();
        if (!C[x]) {
            C[x]++;
            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] << " ";
    }
}