#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int inf = 1e9;
int n, m, x, y, c, dist[50005], fr[50005];
vector <pair<int, int>> v[50005];
priority_queue <pair<int, int>> q;

void dijkstra (int val) {
    for (int i=1; i<=n; ++i)
        dist[i] = inf;
    dist[val] = 0;
    q.push (make_pair(0, val));

    while (!q.empty()) {
        int k = q.top().second;
        int d = -q.top().first;
        q.pop();

        if (fr[k] == 0) {
            for (auto i: v[k])
                if (dist[k] + i.second < dist[i.first]) {
                    dist[i.first] = dist[k] + i.second;
                    q.push (make_pair (-dist[i.first], i.first));
                }
        }
        fr[k] = 1;
    }
}

int main()
{
    f >> n >> m;
    for (int i=1;i<=m; ++i) {
        f >> x >> y >> c;
        v[x].push_back (make_pair (y, c));
    }
    dijkstra (1);

    for (int i=2; i<=n; ++i)
        if (dist[i] != inf)
            g << dist[i] << ' ';
        else
            g << 0 << ' ';
    return 0;
}