#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<bool> vizitat(lv.size(), false);
    vector<int> dist(lv.size(), 1e9);

    dist[0] = 0;
    int nrNoduriVizitate = 0;

    while (nrNoduriVizitate < lv.size()){
        int dMin = 1e9,
            indMin;

        for (int i = 0; i < lv.size(); i++){
            if (vizitat[i] == false && dist[i] < dMin){
                dMin = dist[i];
                indMin = i;
            }
        }

        vizitat[indMin] = true;
        nrNoduriVizitate++;

        for (int i = 0; i < lv[indMin].size(); i++){
            if (vizitat[lv[indMin][i].first] == false && dist[indMin] != 1e9
                && dist[indMin] + lv[indMin][i].second < dist[lv[indMin][i].first])
                dist[lv[indMin][i].first] = dist[indMin] + lv[indMin][i].second;
        }
    }

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