#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m, rez[50009];
vector<pair<int, int>> v[50002];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int main()
{
    memset(rez, 0x3f3f3f3f, sizeof rez);
    f >> n >> m;
    for (int x, y, c; m; m--)
        f >> x >> y >> c, v[x].push_back({y, c});
    rez[1] = 0;
    pq.push({0, 1});
    while (!pq.empty())
    {
        int cst, nod;
        tie(cst, nod) = pq.top();
        if (cst > rez[nod])
            continue;
        pq.pop();
        for (const auto &i : v[nod])
        {
            if (cst + i.second < rez[i.first])
                rez[i.first] = cst + i.second, pq.push({rez[i.first], i.first});
        }
    }
    for (int i = 2; i <= n; i++)
        g << (rez[i] == (0x3f3f3f3f) ? 0 : rez[i]) << " ";
    return 0;
}