#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>

using namespace std;

//TODO: vrea sa vada definitiile si declararile (Mai usor de citit?), mai mult const
//TODO: functiile sa returneze chestii, sa fie facute pentru uz general, nu doar infoarena
//TODO: Havel Hakimi in O(m)
//TODO: de incarcat sursa pe leetcode ptr muchiile critice

struct node_struct {
    int node, cost;
    node_struct(int _node, int _cost): node(_node), cost(_cost) {}
};

//TODO: pot sa merge-uiesc comparCost si node_struct?
struct comparCost {
    bool operator()(node_struct const& n1, node_struct const& n2) { return n1.cost > n2.cost; }
};

class Graf {
    vector<list<node_struct>> listaAdiacenta, transpus;
    void dfs(int nod, vector<int> &vizitate) {
        vizitate[nod] = 1;
        for(auto i: listaAdiacenta[nod])
            if(!vizitate[i.node])
                dfs(i.node, vizitate);
    }
    void bfs(int start, vector<int> &costuri, vector<bool> &vizitate,deque<int> &coada) {
        coada.push_back(start);
        vizitate[start] = true;
        costuri[start] = 0;
        while(coada.empty() != 1) {
            int k = coada.front();
            for(auto i: listaAdiacenta[k])
                if(!vizitate[i.node]) {
                    costuri[i.node] += (costuri[k] + 1);
                    vizitate[i.node] = true;
                    coada.push_back(i.node);
                }
            coada.pop_front();
        }
    }
    void dfsTopo(int nod, vector<bool> &vizitate, stack<int> &rezultat) {
        vizitate[nod] = true;
        for(auto i: listaAdiacenta[nod])
            if(!vizitate[i.node])
                dfsTopo(i.node, vizitate, rezultat);
        rezultat.push(nod);
    }
    void dfsBiconex(int nod, int tata, int &nrSolutii, vector<bool> &vizitate, vector<int> &nivel, vector<int> &nma, stack<int> &stiva, vector<int> solutie[], vector<pair<int,int>> &muchiiCritice) {
        vizitate[nod] = 1;
        nma[nod] = nivel[nod] = nivel[tata] + 1;
        stiva.push(nod);
        for (auto x: listaAdiacenta[nod]) {
            if (x.node != tata){
                if (vizitate[x.node])
                    nma[nod] = min(nma[nod], nivel[x.node]);
                else{
                    dfsBiconex(x.node, nod, nrSolutii, vizitate, nivel, nma, stiva, solutie, muchiiCritice);
                    nma[nod] = min(nma[nod], nma[x.node]);

                    //muchii critice
                    if(nivel[nod] < nma[x.node])
                        muchiiCritice.push_back(make_pair(nod, x.node));

                    //componente biconexe
                    if (nma[x.node] >= nivel[nod]) {
                        nrSolutii++;
                        while (stiva.top() != x.node) {
                            solutie[nrSolutii].push_back(stiva.top());
                            stiva.pop();
                        }
                        solutie[nrSolutii].push_back(x.node);
                        stiva.pop();
                        solutie[nrSolutii].push_back(nod);
                    }
                }
            }
        }
    }
    void dfsConex(int nod, vector<int> &vizitate, stack<int> &s) {
        vizitate[nod] = 1;
        for(auto i: listaAdiacenta[nod])
            if(!vizitate[i.node])
                dfsConex(i.node, vizitate, s);
        s.push(nod);
    }
    void dfsTranspus(int nod, int contor, vector<int> &vizitate, vector<int> *solutie) {
        vizitate[nod] = 2;
        solutie[contor].push_back(nod);
        for(auto j: transpus[nod])
            if(vizitate[j.node] == 1)
                dfsTranspus(j.node, contor, vizitate, solutie);
    }
public:
    Graf(vector<list<node_struct>> _listaAdiacenta, vector<list<node_struct>> _transpuse) : listaAdiacenta(_listaAdiacenta), transpus(_transpuse) {}
    friend ostream& operator<< (ostream& os, Graf graf) {
        os << graf.listaAdiacenta.size() << " nodes\n";
        for(int i = 0; i < graf.listaAdiacenta.size(); i++) {
            os << "node " << i << ": ";
            for(node_struct j: graf.listaAdiacenta[i])
                os << "(" << j.node << ", " << j.cost << ") ";
            os << "\n";
        }
        return os;
    }
    int nrConexe() {
        vector<int> vizitate(listaAdiacenta.size());
        int nr = 0;
        for(int i = 0; i < listaAdiacenta.size(); i++)
            if(!vizitate[i]) {
                nr++;
                dfs(i, vizitate);
            }
        return nr;
    }
    void costuriBFS(int nod, ostream& os = cout) {
        vector<int> costuri(listaAdiacenta.size());
        deque<int> coada;
        vector<bool> vizitate(listaAdiacenta.size());
        bfs(nod, costuri, vizitate, coada);
        for (int i = 0; i < listaAdiacenta.size(); i++) {
            if(vizitate[i])
                os << costuri[i] << " ";
            else os << -1 << " ";
        }
    }
    void sortareTopologica(ostream& os = cout){
        vector<bool> vizitate(listaAdiacenta.size());
        stack<int> rezultat;
        int nr = 0;
        for(int i = 0; i < listaAdiacenta.size(); i++)
            if(!vizitate[i])
                dfsTopo(i, vizitate, rezultat);
        while(rezultat.empty() != 1){
            os << rezultat.top() + 1 << " ";
            rezultat.pop();
        }
    }
    void componenteBiconexe(ostream& os = cout){
        vector<bool> vizitate(listaAdiacenta.size());
        vector<int> nivel(listaAdiacenta.size()), nma(listaAdiacenta.size()),  solutie[listaAdiacenta.size()];
        stack<int> stiva;
        vector<pair<int,int>> muchiiCritice;
        int nrSolutii = 0;
        for (int i = 0; i < listaAdiacenta.size(); i++)
            if (vizitate[i] == 0)
                dfsBiconex(i, 0, nrSolutii, vizitate, nivel, nma, stiva, solutie, muchiiCritice);

        //Componentele biconexe
        os << nrSolutii << "\n";
        for (int i = 1; i <= nrSolutii; i++) {
            for (auto j: solutie[i])
                os << j + 1 << " ";
            os << "\n";
        }

        //Muchiile critice
        for(int i = 0; i < muchiiCritice.size(); i++)
            cout << "(" << muchiiCritice[i].first + 1 << ","<< muchiiCritice[i].second + 1 << ")" << " ";
    }
    void componenteTareConexe(ostream& os = cout) {
        vector<int> vizitate(listaAdiacenta.size()), solutie[listaAdiacenta.size()];
        stack<int> s;
        int contor = 0;
        for(int i = 0; i < listaAdiacenta.size(); i++)
            if(!vizitate[i])
                dfsConex(i, vizitate, s);
        while(s.empty() != 1){
            int nod = s.top();
            if(vizitate[nod] == 1){
                contor++;
                dfsTranspus(nod, contor, vizitate, solutie);
            }
            s.pop();
        }
        os << contor << "\n";
        for(int i = 1; i <= contor; i++){
            for(auto j: solutie[i])
                os << j + 1 << " ";
            os << "\n";
        }
    }
    void dijkstra(int start, ostream& os = cout) {
        vector<int> vizitate(listaAdiacenta.size()), distanta(listaAdiacenta.size(), -1);
        priority_queue<node_struct, vector<node_struct>, comparCost> costuri;
        costuri.push({start, 0});
        distanta[start] = 0;
        while(costuri.empty() != 1) {
            int nod = costuri.top().node;
            costuri.pop();
            if(!vizitate[nod])
                for(auto i: listaAdiacenta[nod]){
                    if(!vizitate[i.node])
                        if(distanta[i.node] == -1 || distanta[i.node] > i.cost + distanta[nod]){
                            distanta[i.node] = i.cost + distanta[nod];
                            costuri.push({i.node, distanta[i.node]});
                        }
                }
            vizitate[nod] = 1;
        }
        for(int i = 0; i < distanta.size(); i++)
            os << distanta[i] << " ";
    }
};

int main() {
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int noduri, muchii, start;
    in >> noduri >> muchii;
//    in >> start; //doar ptr bfs
    vector<list<node_struct>> aux(noduri), aux1(noduri);
    for(int i = 0; i < muchii; i++) {
        int x1, x2, cost;
        in >> x1 >> x2;
        in >> cost;
//        cost = 0;
        node_struct node = {x2 - 1, cost};
        aux[x1 - 1].push_back(node);
//        node = {x1 - 1, cost};
//        aux[x2 - 1].push_back(x1 - 1);  // daca e neorientat
//        aux1[x2 - 1].push_back(x1 - 1); //ptr graful transpus
    }
    Graf graf(aux, aux1);
//    cout << graf.nrConexe(); //ptr DFS
//    graf.costuriBFS(start - 1, out); //ptr BFS
//    graf.sortareTopologica(out);
//    graf.componenteBiconexe(out); // Componente biconexe si muchii critice
//    graf.componenteTareConexe(out);
    graf.dijkstra(0);
    return 0;
}