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

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int INF = (1 << 30), N_MAX = 5e4;

struct Edge {
    int y, cost;
    bool operator<(const Edge &aux) const { return cost > aux.cost; }
};

int n, m, start = 1;
vector<Edge> gr[N_MAX + 5];

int dist[N_MAX + 5];
bool vis[N_MAX + 5];

int main() {
    in >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b, c;
        in >> a >> b >> c;
        gr[a].push_back({b, c});
    }

    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[start] = 0;

    priority_queue<Edge> pq;
    pq.push({start, 0});
    while (!pq.empty()) {
        Edge front = pq.top();

        if (!vis[front.y]) {
            vis[front.y] = true;

            for (auto adj : gr[front.y])
                if (dist[adj.y] > dist[front.y] + adj.cost) {
                    dist[adj.y] = dist[front.y] + adj.cost;
                    pq.push({adj.y, dist[adj.y]});
                }
        }

        pq.pop();
    }

    for (int i = 1; i <= n; i++) {
        if (i == start) continue;

        if (dist[i] == INF)
            out << 0 << ' ';
        else
            out << dist[i] << ' ';
    }
    out << '\n';

    return 0;
}