#include <bits/stdc++.h>
using namespace std;

int main(){
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int n, m, nod1, nod2, cost;

    f >> n >> m;
    vector<vector<pair<int, int>>> lv;

    for (int i = 0; i < n; i++){
        vector<pair<int,int>> aux;
        lv.push_back(aux);
    }
    
    for (int i = 0; i < m; i++){
        f >> nod1;
        f >> nod2;
        f >> cost;
        lv[nod1 - 1].push_back(make_pair(nod2 -1, cost));
    }
    vector<int> dist(lv.size(), 1e9);
    vector<int> vizitat(lv.size(), false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[0] = 0;
    pq.push(make_pair(0,0));

    while (pq.empty() == false) {
        int nod = pq.top().second;
        pq.pop();

        if(vizitat[nod] == false){
            vizitat[nod] = true;
            for (int i = 0; i < lv[nod].size(); i++){
                int nodVecin = lv[nod][i].first;
                int cost = lv[nod][i].second;

                if (dist[nod] + cost < dist[nodVecin])
                    dist[nodVecin] = cost + dist[nod];
                    pq.push(make_pair(dist[nodVecin], nodVecin));
            }
        }
    }

    for (int i = 1; i < lv.size(); i++){
        if (dist[i] == 1e9)
            g << 0 << " ";
        else
            g << dist[i] << " ";
    }
    return 0;
}