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

const int inf = 1e9;
const int nmax = 50000;
int n, m;
vector<pair<int, int>> g[nmax + 1]; // g[u] = { { v, w }, ... }
int dist[nmax + 1];

int main () {

    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    cin >> n >> m ;
    for ( int i = 0; i < m; i ++) {
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back({ v , w }) ;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

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

    int src = 1;
    dist[src] = 0;

    pq.push({ 0, src });

    while (!pq.empty()) {
        // extragem nodul cel mai apropiat
        int d = pq.top().first;
        int u = pq.top().second;

        pq.pop();

        // daca e o intrare outdated (am gasit o distanta
        // mai buna intre timp), abandonam
        if (d > dist[u]) {
            continue;
        }

        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i].first;
            int w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({ dist[v], v });
            }
        }
    }
    

    for ( int i = 2; i <= n; i ++) {
        cout << ( dist [i] == inf ? -1 : dist [i ]) << " ";
    }
    return 0;
}