#include <bits/stdc++.h>
#include <vector>
#include <set>

#define NMAX (int)(5e5 + 5)
#define INF 0x3f3f3f3f

using namespace std;

int n, m;
vector<pair<int, int>> g[NMAX]; //pair<to, cost>
int dist[NMAX];
set<pair<int, int>> unvisited; //pair<cost, to>

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; ++i) {
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        g[from].push_back(make_pair(to, cost));
    }

    memset(dist, INF, sizeof dist);
    dist[1] = 0;
    unvisited.insert(make_pair(0, 1));

    while (!unvisited.empty()) {
        int curr = unvisited.begin()->second;
        unvisited.erase(unvisited.begin());

        for (pair<int, int> next : g[curr]) {
            int to = next.first;
            int cost = next.second;

            if (dist[curr] + cost < dist[to]) {
                if (dist[to] != INF)
                    unvisited.erase(unvisited.find(make_pair(dist[to], to)));

                dist[to] = dist[curr] + cost;
                unvisited.insert(make_pair(dist[to], to));
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF) dist[i] = 0;
        printf("%d ", dist[i]);
    }

    printf("\n");
    return 0;
}