#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
using namespace std;

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

const int INF = 2000000000;
// structura grafului adj[nod] = {vecin, cost}
vector<pair<int ,int> > adj[50005];
int dist[50005];
int N,M;
void dijkstra(int startNode) {
    for (int i = 1; i <= N; i++) {
        dist[i] = INF;
    }

    dist[startNode] = 0;
    // Min-Heap (priority queue) care tine elementul cel mai mic in varf
    // perechi {dist, nod}
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

    pq.push(make_pair(0, startNode));

    while (!pq.empty()) {
        // extrag nodul cu distanta minima
        int currentDist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (currentDist > dist[u]) continue;
        // vecinii nodului curent
        for (auto edge : adj[u]) {
            int v = edge.first;
            int cost = edge.second;

            // relaxarea muchiilor
            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}
int main() {
    fin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        adj[u].push_back(make_pair(v,w));
    }

    dijkstra(1);

    for (int i = 2; i <= N; i++) {
        if (dist[i] == INF) {
            fout << 0 << " ";
        }
        else {
            fout << dist[i] << " ";
        }
    }
    return 0;
}