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

constexpr int maxn = 1 << 16;

vector<pair<int, int>> v[maxn];
int dist[maxn] = {}, q[maxn] = {};
unsigned short st = 0, dr = 0;
bool in_q[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[dr++] = 1;
    in_q[1] = 1;

    while (st != dr) {
        int x = q[st++];
        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[st]])
                    q[--st] = y.first;
                else
                    q[dr++] = y.first;
            }
        }
    }

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

    return 0;
}