#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1 << 16;

vector<pair<int, int>> v[maxn];
deque<int> q;
bool in_q[maxn] = {};
int dist[maxn] = {};

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int n, m;
    f >> n >> m;

    while (m--) {
        int x, y, z;
        f >> x >> y >> z;

        v[x].emplace_back(y, z);
    }

    memset(dist, 0x3f, sizeof(dist));

    dist[1] = 0;
    q.push_back(1);
    in_q[1] = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop_front();
        in_q[x] = 0;

        for (auto y : v[x]) {
            if (dist[y.first] > dist[x] + y.second) {
                dist[y.first] = dist[x] + y.second;

                if (in_q[y.first])
                    continue;

                in_q[y.first] = true;
                if (dist[y.first] <= dist[q.front()])
                    q.push_front(y.first);
                else
                    q.push_back(y.first);
            }
        }
    }

    for (int i = 2; i <= n; ++i)
        g << (dist[i] == 0x3f3f3f3f ? 0 : dist[i]) << ' ';

    return 0;
}