#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <int> dijkstra(vector <vector <pair <int, int>>>& edges, int src = 1)
{
    int n = edges.size();
    const int MAX = 1e9 + 5;
    vector <int> dist(n, MAX);

    priority_queue<pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;
    pq.push({0, src});
    dist[src] = 0;

    while (!pq.empty()) {
        int cost = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if (cost != dist[node]) continue;

        for (auto it : edges[node]) {
            int node1 = it.first;
            int cost1 = it.second;

            if (cost + cost1 < dist[node1]) {
                dist[node1] = cost + cost1;
                pq.push({dist[node1], node1});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] == MAX) dist[i] = 0;
    }

    return dist;
}

int main()
{
    int n, m;
    fin >> n >> m;

    vector <vector <pair <int, int>>> edges(n + 1);
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        edges[a].push_back({b, c});
    }

    vector <int> dist = dijkstra(edges);
    for (int i = 2; i <= n; i++) {
		fout << dist[i] << " ";
	}
    return 0;
}