#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5e4;
vector<pair<int, int>> g[NMAX + 5];
int dist[NMAX + 5];

int main() {
    #ifndef TEST 
        freopen("dijkstra.in", "r", stdin);
        freopen("dijkstra.out", "w", stdout);
    #endif
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
    }
    for (int i = 2; i <= n; i++)
        dist[i] = -1;
    dist[1] = 0;
    priority_queue<pair<int, int>> pq;
    pq.emplace(0, 1);
    while (!pq.empty()) {
        pair<int, int> current = pq.top();
        pq.pop();
        int distance = -current.first, node = current.second;
        if (distance != dist[node])
            continue;
        for (auto edge : g[node]) {
            int newNode = edge.first, newCost = edge.second + dist[node];
            if (dist[newNode] == -1 || dist[newNode] > newCost)
                dist[newNode] = newCost, pq.emplace(-newCost, newNode);
        }
    }
    for (int i = 2; i <= n; i++)
        cout << dist[i] << ' ';
    return 0;
}