#include <bits/stdc++.h>

using namespace std;

int n, m, dmin[50005];
vector<pair<int, int>> adj[50005];

struct Heap{
    pair<int, int> h[250005];
    int curr_poz = 0;
    void insertion(int x, int dist){
        h[++curr_poz] = {x, dist};
        int poz = curr_poz;
        while(poz != 1 && h[poz].second > h[poz / 2].second){
            swap(h[poz], h[poz / 2]);
            poz /= 2;
        }
    }
    void poptop(){
        swap(h[1], h[curr_poz]);
        curr_poz--; //rip
        int poz = 1;
        while(poz * 2 <= curr_poz){
            if(poz * 2 == curr_poz){
                swap(h[poz], h[poz * 2]);
                poz *= 2;
                continue;
            }
            if(h[poz * 2].second >= h[poz * 2 + 1].second){
                swap(h[poz * 2], h[poz]);
                poz *= 2;
            }
            else{
                swap(h[poz * 2 + 1], h[poz]);
                poz = poz * 2 + 1;
            }
        }
    }
}heap;

void dijkstra(){
    dmin[1] = 0;
    for(int i = 2; i <= n; i++) dmin[i] = 1e9;
    heap.insertion(1, 0);
    while(heap.curr_poz){
        int i = heap.h[1].first, d = heap.h[1].second;
        heap.poptop();
        if(d > dmin[i]) continue;
        for(auto [j, cost] : adj[i]){
            if(dmin[j] > d + cost){
                dmin[j] = d + cost;
                heap.insertion(j, dmin[j]);
            }
        }
    }
}

int main(){

    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
    }

    dijkstra();

    for(int i = 2; i <= n; i++){
        if(dmin[i] == 1e9) cout << 0 << " ";
        else cout << dmin[i] << " ";
    }

    return 0;
}