#include  <bits/stdc++.h>

using namespace std;

int main() {

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

    int n,m;



    cin >> n >> m;

    vector<vector<pair<int,int>>> graf(n+1);



    while (m--) {
        int a,b,c;
        cin >> a >> b >> c;

        graf[a].push_back({b,c});
    }

    vector<int> dist(n+1,1e9);
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    pq.push({0,1});
    dist[1] = 0;

    while (!pq.empty()) {
        pair<int,int> curr = pq.top();
        pq.pop();

        if (curr.first > dist[curr.second]) {
            continue;
        }

        for (auto edge : graf[curr.second]) {
            if (curr.first+edge.second < dist[edge.first]) {
                dist[edge.first] = curr.first+edge.second;
                pq.push({dist[edge.first],edge.first});
            }
        }
    }

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

    return 0;
}