#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]; //nod, distanta
    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 >> 1].second){
            swap(h[poz], h[poz >> 1]);
            poz >>= 1;
        }
    }
    void poptop(){
        swap(h[1], h[curr_poz]);
        curr_poz--; //rip
        int poz = 1;
        while(poz << 1 <= curr_poz){
            if(poz << 1 == curr_poz && h[poz].second > h[poz << 1].second){
                swap(h[poz], h[poz << 1]);
                break;
            }
            if(h[poz].second < h[poz << 1].second && h[(poz << 1) | 1].second > h[poz].second)
                break;
            else if(h[poz << 1].second <= h[(poz << 1) | 1].second){
                swap(h[poz << 1], h[poz]);
                poz <<= 1;
            }
            else{
                swap(h[(poz << 1) | 1], h[poz]);
                poz = (poz << 1) | 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;
}