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

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

class cmp{
public:
    bool operator() (pair<int, int> &a, pair<int, int>&b){
        return a.second > b.second;
    }
};

class Graf{
    int nr_noduri, nr_muchii;
    const int inf = INT_MAX;
public:


    //lista drumurilor minime de la un nod dat
    void BellmanFord(const int start);

    //Dijkstra
    void Dijkstra(const int start);
};



void Graf ::BellmanFord(const int start) {
    in >> nr_noduri >> nr_muchii;
    vector<pair<int, int>> lista_muchii[nr_noduri+1];
    vector<int> d(nr_noduri+1,inf);

    d[start] = 0;
    for(int i = 1; i <= nr_muchii; ++i){
        int x,y,cost;
        in >> x >> y >> cost;
        lista_muchii[x].push_back({y,cost});

    }

            //relaxam de N-1 ori nodurile
    for(int j = 1; j <= nr_noduri-1; ++j){
        for(int i = 1; i <= nr_noduri; ++i)
            for(auto val : lista_muchii[i])
            {
                if(d[val.first] > d[i] + val.second)
                    d[val.first] = d[i] + val.second;
            }
    }
    for(int i = 2; i <= nr_noduri; ++i) {
        if (d[i] == inf)
            d[i] = 0;

        out << d[i] << " ";
    }
}

void Graf::Dijkstra(const int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    in >> nr_noduri >> nr_muchii;
    vector<int> d(nr_noduri+1, inf);
    vector<bool> vizitat(nr_noduri+1, false);
    d[start] = 0;
    vector<pair<int, int>> lista_muchii[nr_noduri+1];
    for(int i = 1; i <= nr_muchii; ++i){
        int x, y,cost;
        in >> x >> y >> cost;
        lista_muchii[x].push_back({y,cost});

    }

    pq.push({start,d[start]});

    while (pq.size()) {
        int nod = pq.top().first;
        int cost = pq.top().second;
        pq.pop();
        if (!vizitat[nod]) {
            vizitat[nod] = true;
            for (auto val : lista_muchii[nod])
                if (d[val.first] > d[nod] + val.second) {
                    d[val.first] = d[nod] + val.second;
                    pq.push({val.first, d[val.first]});
                }
        }
    }

    for(int i = 2; i <= nr_noduri; ++i) {
        if(d[i] == inf)
            d[i] = 0;

        out << d[i] << " ";
    }

}


int main() {

    Graf g;
    g.Dijkstra(1);
    return 0;
}