#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define cin fin
//#define cout fout

struct el {
    long long nod, cost;
    bool operator <(const el &other) const {
        return cost > other.cost;
    }
};

int sursa;
vector<vector<el>> adj;
vector<long long> dist;
priority_queue<el> pq;

void dijkstra() {
    dist[sursa] = 0;
    pq.push({sursa, 0});

    while(!pq.empty()) {
        el curr = pq.top();
        pq.pop();
        long long u = curr.nod;
        long long u_c = curr.cost;
        if(u_c > dist[u]) continue;

        for(auto e : adj[u]) {
            long long v = e.nod;
            long long v_c = e.cost;

            if(dist[u] + v_c < dist[v]) {
                dist[v] = dist[u] + v_c;
                pq.push({v, dist[v]});
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    adj.resize(n + 1);
    dist.resize(n + 1);
    fill(dist.begin(), dist.end(), 1e18);
    for(int i = 1; i <= m; i++) {
        long long x, y, c;
        cin >> x >> y >> c;
        adj[x].push_back({y, c});
    }
    sursa = 1;
    dijkstra();

    for(int i = 2; i <= n; i++) {
        cout << dist[i] << " ";
    }
}