#include<bits/stdc++.h>

#define cin in
#define cout out
using namespace std;

typedef pair<int,int> iiPair;

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

void dijkstra(int src, int n, vector<vector<iiPair>> &graph){
    vector<int> dist(n,INT_MAX);
    set<iiPair> pq;

    pq.emplace(0,src);
    dist[src] = 0;

    while(!pq.empty()){
        int u = pq.begin()->second;
        pq.erase(pq.begin());

        for(auto it : graph[u]){
            int v = it.first;
            int w = it.second;

            if(dist[v] > dist[u] + w){
                if(dist[v] != INT_MAX)
                    pq.erase(pq.find({dist[v],v}));
                dist[v] = dist[u] + w;
                pq.emplace(dist[v],v);
            }
        }
    }

    for(int i = 1; i < n; ++i){
        cout << (dist[i] != INT_MAX ? dist[i] : 0) << ' ';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, x, y, w;

    cin >> n >> m;

    vector<vector<iiPair>> graph(n);

    while(m--){
        cin >> x >> y >> w;
        graph[x - 1].emplace_back(y - 1,w);
    }

    dijkstra(0,n,graph);
}