#include<bits/stdc++.h>

using namespace std;

int n, m, dist[250000]; // varfuri, muchii

vector<pair<int,int>>nod[250000];

int main(){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    cin >> n >> m;
    
    for(int i=1;i<=m;i++){
        int x, y, z;
        cin >> x >> y >> z; // x ---- y - lungimea z;
        nod[x].push_back({y, z});
    }

    for(int i=1;i<=n;i++){
        dist[i] = 1e9;
    }
    dist[1] = 0;

    multiset<pair<int,int>>s;

    s.insert({0, 1});
    
    while(s.size() >= 1){

        auto curr = *s.begin();
        s.erase(s.begin());

        int distanta = curr.first;
        int nod_curr = curr.second;

        if(distanta > dist[nod_curr]) continue;

        for(auto it : nod[nod_curr]){
            if(it.second + distanta < dist[it.first]){
                dist[it.first] = it.second + distanta;
                s.insert({dist[it.first], it.first});
            }
        }
        
    }

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