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

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

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

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

}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i) {
        f >> x >> y >> c;
        G[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;
}