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

typedef pair<long long, long long> pll;

int main() {
    int n, m; 
    // n = cities, m = flights
    cin >> n >> m;

    vector<pll> adj[n+1];

    for (int i=0; i<m; i++) {
        long long a, b, c;
        // flight from a to b with cost c
        cin >> a >> b >> c;
        adj[a].push_back( {b, c} );
    }

    vector<long long> dist(n+1, LLONG_MAX);

    // minimum priority queue
    priority_queue< pll , vector<pll>, greater<pll> > pq; // smallest item first
    // {dist, nodeNumber}
    pq.push( {0, 1} ); 

    while(!pq.empty()) {
        pll x = pq.top();
        pq.pop();
        long long d = x.first , cur = x.second;

        if (d >= dist[cur]) continue; // if (vis[cur]) continue
        dist[cur] = d; // vis[cur] = true

        // for each adjacent node of cur
        for (pll x: adj[cur]) {
            long long v = x.first, c = x.second;
            long long newDist = d + c;
            if (newDist >= dist[v]) continue;
            pq.push({newDist, v});
        }
    }

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