#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/priority_queue.hpp>

using namespace std;
using namespace  __gnu_pbds; 

typedef __gnu_pbds::priority_queue<pair<int, int>, greater<pair<int, int>>> PairingHeap;

const int MAXN = 100000;

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, m; cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; ++i) {
        int x, y, c; cin >> x >> y >> c;
        x--; y--;
        adj[x].emplace_back(make_pair(y, c));
    }
    
    PairingHeap heap;
    vector<PairingHeap::point_iterator> where(n, NULL);
    vector<int> dist(n, numeric_limits<int>::max());
    
    dist[0] = 0;
    where[0] = heap.push({0, 0});
    while (!heap.empty()) {
        pair<int, int> state = heap.top();
        heap.pop();
        
        where[state.second] = NULL;
        for (const auto& e: adj[state.second]) {
            const int son = e.first;
            const int cost = state.first + e.second;
            
            if (dist[son] > cost) {
                dist[son] = cost;
                
                if (where[son] == NULL) {
                    where[son] = heap.push({dist[son], son});
                } else {
                    heap.modify(where[son], {dist[son], son});
                }
            }
        }
    }
    
    for (int i = 1; i < n; ++i) {
        if (dist[i] == numeric_limits<int>::max()) {
            dist[i] = 0;    
        }
        
        cout << dist[i] << " \n"[i + 1 == n];
    }
}