#include <fstream>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

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

class Graf
{
    int nrNoduri;
    int nrMuchii;
    bool orientat;

    vector<list<int>> listaAdiacenta;
    vector<list<pair<int, int>>> listaMuchii; // vector[1] = {(2, 1), (4, 7)}    -->    explicatie:   *1 --- 1 --> *2 ,   *1 --- 7 --> *4


public:

    Graf(bool o = false, int n = 0, int m = 0)
    {
        nrNoduri = n;
        nrMuchii = m;
        orientat = o;
    }

    void citireListaAdiacenta()
    {
        listaAdiacenta.resize(nrNoduri + 1);

        int x, y;
        for (int i = 0; i < nrMuchii; i++)
        {
            fin >> x >> y;
            listaAdiacenta[x].push_back(y);

            if(!orientat)
                listaAdiacenta[y].push_back(x);
        }
    }

    void citireListaMuchii()
    {
        listaMuchii.resize(nrNoduri + 1);

        int x, y, c;
        for (int i = 0; i < nrMuchii; i++)
        {
            fin >> x >> y >> c;
            listaMuchii[x].push_back(make_pair(y, c));

            if (!orientat)
                listaMuchii[x].push_back(make_pair(x, c));
        }
    }

    void afisareListaAdiacenta()
    {
        fout << "\nnrNoduri = " << nrNoduri;
        fout << "\nnrMuchii = " << nrMuchii;

        fout << "Lista de adiacenta asociata grafului <G>:\n\n\n";
        for (int i = 1; i <= nrNoduri; i++)
        {
            if (listaAdiacenta[i].size() > 0)
            {
                fout << i << " : ";
                for (int x : listaAdiacenta[i])
                    fout << x << " ";
                fout << "\n\n";
            }
        }
    }

    void afisareListaMuchii()
    {
        fout << "\nnrNoduri = " << nrNoduri;
        fout << "\nnrMuchii = " << nrMuchii;

        fout << "\n\nLista de MUCHII asociata grafului <G>:\n\n";
        for (int i = 1; i <= nrNoduri; i++)
        {
            fout << "Nod " << i << ":\n";
            for (auto x : listaMuchii[i])
                fout << "    " << i << " --> " << x.second << " --> " << x.first <<"\n";
            fout << "\n\n";
        }
    }


    vector<int> distanteBFS(int nodS)
    {
        vector<bool> vizitat(nrNoduri + 1, false);
        vector<int> distanta(nrNoduri + 1, -1);

        BFS(nodS, vizitat, distanta);

        return distanta;
    }

    list<set<int>> componenteConexe()
    {
        list<set<int>> listaCC;
        set<int> componentaConexa;

        vector<bool> vizitat(nrNoduri + 1, false);

        for (int i = 1; i <= nrNoduri; i++)
            if (!vizitat[i])
            {
                DFS(i, componentaConexa, vizitat);
                listaCC.push_back(componentaConexa);
                componentaConexa.clear();
            }

        return listaCC;
    }

    list<set<int>> componenteTareConexe()
    {
        list<set<int>> listaCTC;

        vector<int> discOrder(nrNoduri + 1, 0); // nodul x este al discOrder[x]-lea nod obtinut din parcurgerea DFS
        vector<int> lowLink(nrNoduri + 1, 0); // lowLink[x] = min(lowLink[x], discOrder[y]), cu Y conectat la X
        vector<bool> onStack(nrNoduri + 1, false);
        stack<int> stack; // stiva care valideaza apartenenta unui nod la o componenta conexa

        for (int i = 1; i <= nrNoduri; i++)
            if (discOrder[i] == 0)
                TareConexDFS(i, listaCTC, discOrder, lowLink, stack, onStack);

        return listaCTC;
    }

    list<set<int>> componenteBiconexe()
    {
        list<set<int>> listaCBC;

        vector<int> adancimi(nrNoduri + 1, 0);
        vector<int> lowLink(nrNoduri + 1, 0); // adancimea maxima pe care o poate atinge un nod prin descendenti
        vector<bool> vizitat(nrNoduri + 1, 0);
        stack<int> stack;

        BiconexDFS(1, 1, stack, vizitat, adancimi, lowLink, listaCBC);

        return listaCBC;
    }

    list<pair<int, int>> muchiiCritice()
    {
        list<pair<int, int>> listaMC;

        vector<int> discOrder(nrNoduri + 1, 0); // nodul x este al discOrder[x]-lea nod obtinut din parcurgerea DFS
        vector<int> lowLink(nrNoduri + 1, 0); // lowLink[x] = min(lowLink[x], discOrder[y]), cu Y conectat la X

        MCriticeDFS(1, 0, listaMC, discOrder, lowLink);

        return listaMC;
    }

    list<int> sortareTopologica()
    {
        list<int> listaTP;
        vector<bool> vizitat(nrNoduri + 1, false);

        for (int i = 1; i <= nrNoduri; i++)
            if (!vizitat[i])
                topologicDFS(i, listaTP, vizitat);

        return listaTP;
    }

    bool HavelHakimi()
    {
        vector<int> grade;

        int gr;
        while (fin >> gr)
        {
            grade.push_back(gr);
        }

        while (1)
        {
            sort(grade.begin(), grade.end(), greater<>());

            if (grade[0] == 0)
                return true;

            if (grade[0] > grade.size() - 1)
                return false;

            for (int i = 1; i <= grade[0]; i++)
            {
                grade[i]--;

                if (grade[i] < 0)
                    return false;
            }

            grade.erase(grade.begin() + 0);
        }
    }

    vector<int> distanteDijkstra(int nodS)
    {
        vector<int> distanta(nrNoduri + 1, 0x3f3f3f3f);
        set<pair<int, int>> inProcesare; // multime de perechi (distanta, nod) ordonata dupa distanta

        distanta[nodS] = 0;
        inProcesare.insert(make_pair(0, nodS));

        while (!inProcesare.empty())
        {
            int top = (*(inProcesare.begin())).second;
            inProcesare.erase(inProcesare.begin());

            for (auto x : listaMuchii[top])
            {
                int n2 = x.first;
                int c = x.second;

                if (distanta[n2] > distanta[top] + c)
                {
                    if (distanta[n2] != 0x3f3f3f3f)
                        inProcesare.erase(inProcesare.find(make_pair(distanta[n2], n2)));

                    distanta[n2] = distanta[top] + c;
                    inProcesare.insert(make_pair(distanta[n2], n2));
                }
            }
        }

        return distanta;
    }


private:

    void BFS(int nodS, vector<bool>& vizitat, vector<int>& distanta)
    {
        queue<int> queue;
        queue.push(nodS);

        vizitat[nodS] = true;
        distanta[nodS] = 0;

        while (!queue.empty())
        {
            int nodCurent = queue.front();

            queue.pop();

            for (auto vecin : listaAdiacenta[nodCurent])
                if (!vizitat[vecin])
                {
                    queue.push(vecin);
                    vizitat[vecin] = true;
                    distanta[vecin] = distanta[nodCurent] + 1;
                }
        }
    }

    void DFS(int nodS, set<int>& componentaConexa, vector<bool>& vizitat)
    {
        vizitat[nodS] = true;
        componentaConexa.insert(nodS);

        for (auto vecin : listaAdiacenta[nodS])
            if (!vizitat[vecin])
                DFS(vecin, componentaConexa, vizitat);
    }

    void TareConexDFS(int nodS, list<set<int>>& listaCTC, vector<int>& discOrder, vector<int>& lowLink, stack<int>& stack, vector<bool>& onStack)
    {
        static int idCurent = 1;
        stack.push(nodS);
        onStack[nodS] = true;
        discOrder[nodS] = lowLink[nodS] = idCurent++;

        for (auto x : listaAdiacenta[nodS])
        {
            if (discOrder[x] == 0) // daca nodul nu a fost explorat, pornim DFS din el, iar la revenirea din recursie, il incadram intr-o componenta conexa;
            {
                TareConexDFS(x, listaCTC, discOrder, lowLink, stack, onStack);
                lowLink[nodS] = min(lowLink[nodS], lowLink[x]);
            }
            else // daca nodul a fost explorat si se afla pe stiva de validare, il incadram intr-o componenta conexa;
                if (onStack[x])
                    lowLink[nodS] = min(lowLink[nodS], discOrder[x]);
        }

                                               // daca ID - ul nodului corespunde cu lowLink - value - ul sau, inseamna ca nodul este radacina componentei sale conexe,
        if (lowLink[nodS] == discOrder[nodS])  // si putem scoate de pe stiva toate nodurile pana la nodS, deoarece am terminat de explorat componenta respectiva;
        {
            set<int> componentaConexa;
            int top;
             
            do
            {
                top = stack.top();
                stack.pop();
                onStack[top] = false;

                componentaConexa.insert(top);
            } while (nodS != top);

            listaCTC.push_back(componentaConexa);
        }
    }

    void BiconexDFS(int nodS, int adancimeCurenta, stack<int>& stack, vector<bool>& vizitat, vector<int>& adancimi, vector<int>& lowLink, list<set<int>>& listaCBC)
    {
        stack.push(nodS); // stiva retine parcurgerea DFS a subarborilor grafului
        vizitat[nodS] = true;
        adancimi[nodS] = lowLink[nodS] = adancimeCurenta; // adancimi[x] = nivelul de adancime al nodului X din arborele DFS;     lowLink[x] = adancimea minima la care se poate intoarce nodul X;

        for (auto x : listaAdiacenta[nodS])
        {
            if (vizitat[x])
                lowLink[nodS] = min(lowLink[nodS], adancimi[x]); // adancimea minima a nodului curent S = min (adancimea sa minima curenta; adancimea vecinilor sai)
            else
            {
                BiconexDFS(x, adancimeCurenta + 1, stack, vizitat, adancimi, lowLink, listaCBC);
                lowLink[nodS] = min(lowLink[nodS], lowLink[x]); // la intoarcerea din recursie, nodurile cu adancimea < adancimea nodului pe care s-a facut recursia
                                                                // isi minimizeaza adancimea minima lowLink cu a succesorilor;
                if (lowLink[x] == adancimi[nodS])
                {                                   // cand ajungem la succesorul radacinii componentei, eliminam nodurile pana la radacina din stiva, formand o componenta biconexa;
                    set<int> componentaBiconexa;
                    int top;

                    do
                    {
                        top = stack.top();
                        stack.pop();

                        componentaBiconexa.insert(top);
                    } while (x != top);

                    componentaBiconexa.insert(nodS);
                    listaCBC.push_back(componentaBiconexa);
                }
            }
        }
    }

    void MCriticeDFS(int nodS, int parinte, list<pair<int, int>>& listaMC, vector<int>& discOrder, vector<int>& lowLink)
    {
        static int idCurent = 1;
        discOrder[nodS] = lowLink[nodS] = idCurent++;

        for (int copil : listaAdiacenta[nodS])
        {
            if (discOrder[copil] == 0)
            {
                MCriticeDFS(copil, nodS, listaMC, discOrder, lowLink);

                lowLink[nodS] = min(lowLink[nodS], lowLink[copil]);

                if (lowLink[copil] > discOrder[nodS])
                    listaMC.push_back(make_pair(nodS, copil));
            }
            else
                if (copil != parinte)
                    lowLink[nodS] = min(lowLink[nodS], discOrder[copil]);
        }
    }

    void topologicDFS(int nodS, list<int>& ordine, vector<bool>& vizitat)
    {
        vizitat[nodS] = true;

        for (auto vecin : listaAdiacenta[nodS])
            if (!vizitat[vecin])
                topologicDFS(vecin, ordine, vizitat);

        ordine.push_front(nodS);
    }
};


int main()
{
    int n, m, s;
    fin >> n >> m;

    Graf G(true, n, m);
    //Graf G(false);

    G.citireListaMuchii();
    //G.afisareListaMuchii();

/* ---> DISTANTE BFS <--- */
    /*vector<int> DistMIN = G.distanteBFS(s);

    for (auto x : DistMIN)
        fout << x << " ";*/

/* ---> COMPONENTE CONEXE <--- */
    /*vector<set<int>> CC = G.componenteConexe();

    fout << CC.size();*/

/* ---> COMPONENTE TARE CONEXE <--- */
    /*vector<set<int>> CTC = G.componenteTareConexe();

    fout << CTC.size() << "\n";

    for (int i = 0; i < CTC.size(); i++)
    {
        for (auto x : CTC[i])
            fout << x << " ";
        fout << "\n";
    }*/

/* ---> COMPONENTE BICONEXE <--- */
    /*vector<set<int>> CBC = G.componenteBiconexe();

    fout << CBC.size() << "\n";

    for (int i = 0; i < CBC.size(); i++)
    {
        for (auto x : CBC[i])
            fout << x << " ";
        fout << "\n";
    }*/

/* ---> MUCHII CRITICE <--- */
    /*vector<pair<int, int>> MC = G.muchiiCritice();

    fout << MC.size() << "\n";

    for (int i = 0; i < MC.size(); i++)
    {
        for (auto x : MC)
            fout << x.first << " " << x.second;
        fout << "\n";
    }*/

/* ---> SORTARE TOPOLOGICA <--- */
    /*list<int> TP = G.sortareTopologica();

    for (auto x : TP)
        fout << x << " ";*/

/* ---> HAVEL HAKIMI <-- - */
    /*bool HH = G.HavelHakimi();

    HH ? fout << "Yes" : fout << "No";*/

/* ---> DISTANTE DIJKSTRA <--- */
    vector<int> DJK = G.distanteDijkstra(1);

    for (int i = 2; i < DJK.size(); i++)
    {
        if (DJK[i] == 0x3f3f3f3f)
            DJK[i] = 0;
       
        fout << DJK[i] << " ";
    }
}