#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()) {
        int currDist = pq.top().first,currNode = pq.top().second;
        pq.pop();

        if (currDist > dist[currNode]) {
            continue;
        }

        for (auto [targetNode,weight] : graf[currNode]) {
            if (currDist+weight < dist[targetNode]) {
                dist[targetNode] = currDist+weight;
                pq.push({dist[targetNode],targetNode});
            }
        }

    }

    for (int i = 2;i<=n;i++) {
        cout << ((dist[i] == 1e9)?0:dist[i]) << " ";
    }




    return 0;

}