#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cassert>
#include <stack>
#include <set>

using namespace std;

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

//clasa de multimi disjuncte folosita la algoritmul lui Kruskal
class DisjointSets
{
private:
    int n; //numarul de noduri
    vector<int> rep; //vectorul de reprezentanti(conform cursului)
    vector<int> h; //vector ce va retine inaltimile arborilor

public:
    DisjointSets(int n);//constructor parametrizat care face si initializarea vectorului de preprezentanti
    int Reprezentant(int x);//metoda ce returneaza reprezentantul unui nod x dat
    void Reuniune(int x, int y);//metoda ce reuneste arborii care contin nodurile x si y

};

DisjointSets::DisjointSets(int n)
{
    this->n = n;
    //initializam vectorul de reprezentanti si pe cel de inaltimi
    rep.resize(n+1);
    h.resize(n+1);
    for(int i=1; i<=n; ++i)
        rep[i] = i;
};

int DisjointSets::Reprezentant(int x)
{
    //daca x este chiar radacina(adica daca el este reprezentantul sau) il returnez
    if(x == rep[x])
        return x;
    else //altfel reprezentantul lui x va fi reprezentantul tatalui sau(apel recursiv)
    {
        //efectuam compresia asupra arborelui
        int r = Reprezentant(rep[x]); //aflu reprezentantul parintelui lui x
        rep[x] = r;
        //returnam reprezentantul lui x
        return r;
    }
}

void DisjointSets::Reuniune(int x, int y)
{
    //aflam rep lui x si y
    int rx = Reprezentant(x);
    int ry = Reprezentant(y);

    //daca x si y au acelasi reprezentant, atunci acestia sunt deja in aceeasi multime(nu am ce sa reunesc)
    if(rx == ry)
        return;

    //subordonez reprezentantul din arborele cu inaltime mai mica reprezentantului din arborele cu inaltime mai mare
    if(h[rx] < h[ry])
        rep[rx] = ry;
    else if(h[rx] > h[ry])
        rep[ry] = rx;
    else //au inaltimi egale caz in care inaltimea creste cu 1 dupa subordonare
    {
        rep[rx] = ry;
        h[ry]++;
    }

}

//strucutra unui arc cu distanta(cost) din graf(folosita in metodele Dijkstra si Bellman_Ford)
struct arc
{
    int y, distanta;
    arc(int b, int d)
    {
        y = b;
        distanta = d;
    }
    arc(){}
    bool operator < (const arc &a) const //operator pentru compararea distantelor(costurilor) a doua arce
    {return distanta < a.distanta;}
};


//clasa Min_heap folosita la pastrarea in ordinea crescatoare a distantelor(costurilor) a arcelor din graf (folosita in metoda Dijsktra)
class Min_heap
{
private:
    int n; //nr de noduri din heap
    int N; //numarul de noduri distincte din heap
    vector<arc> h; //vector de arce prin care este reprezentat heap-ul
    vector<int> pozitii; //vector ce retine pe ce pozitie in heap se afla fiecare nod x

public:
    Min_heap(int n); //constructor parametrizat pt heap
    arc pop(); //metoda care scoate minimul din heap(varful)
    void push(arc a); //metoda care insereaza in heap un arc
    void go_down(int i, int n); //metoda de deplasare in jos in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
    void go_up(int i); //metoda de deplasare in sus in heap(folosita cand se extrage sau se insereaza cate un arc, pt a mentine prop de min-heap)
    int poz_min(int i, int n); //metoda care obtine pozitia fiului minim al unui nod abia inserta in heap
    bool empty(); //metoda care testeaza daca heap-ul este gol
};

bool Min_heap::empty()
{
    if(N==0)
        return true;
    else
        return false;
}


Min_heap::Min_heap(int n)
{
    h.resize(n+1);
    pozitii.resize(n+1);
    N = 0;
}

int Min_heap::poz_min(int i, int n)
{
    if(2*i>n) //daca nodul este frunza
        return 0;

    if(2*i + 1 <= n) //daca nodul nu este frunza si exista ambii descendent
    {
        if(h[2*i].distanta <= h[2*i+1].distanta)
            return 2*i;
        else
            return 2*i+1;
    }
    else //nodul nu este frunza dar am doar descendent stang
        return 2*i;

}

void Min_heap::go_up(int i)
{
    if(i>1) //daca nodul nu este deja in varf
    {
        int p = i/2; //aflu parintele
        if(h[i] < h[p])
        {
            pozitii[h[i].y] = p;
            pozitii[h[p].y] = i;
            arc aux = h[p];
            h[p] = h[i];
            h[i] = aux;
            go_up(p);
        }
    }
}

void Min_heap::go_down(int i, int n)
{
    if(i<=n/2) //daca nodul nu este deja frunz
    {
        int m = poz_min(i,n); //aflu pozitia celui mai mic dintre fii
        if(h[m] < h[i])
        {
            pozitii[h[i].y] = m;
            pozitii[h[m].y] = i;
            arc aux = h[m];
            h[m] = h[i];
            h[i] = aux;
            go_down(m, n);
        }
    }
}

arc Min_heap::pop()
{
    pozitii[h[N].y] = 1;
    pozitii[h[1].y] = 0;
    arc aux = h[1];
    h[1] = h[N];
    h[N] = aux;
    N--;
    go_down(1, N);
    return h[N+1];

}

void Min_heap::push(arc a)
{
    //daca nodul y deja exista in heap il elimin, pentru a ne asigura ca un nod nu apare de mai multe ori in heap
    if(pozitii[a.y]>0)
    {
        arc aux = h[pozitii[a.y]];
        pozitii[h[N].y] = pozitii[a.y];
        h[pozitii[a.y]] = h[N];
        h[N] = aux;
        N--;
        go_down(pozitii[a.y], N);
    }
    //adaug noul nod in heap si memorez pozitia sa
    N++;
    h[N] = a;
    pozitii[a.y] = N;
    go_up(N);

}


class Graf
{
private:
    //strucutra unei muchii din graf(folosita in medota Biconexe)
    struct muchie
    {
        int x,y;
        muchie(int a, int b)
        {
            x=a;
            y=b;
        }
        muchie(){}
    };
    //strucutra unei muchii cu cost din graf(folosita in medota Kruskal)
    struct muchie_cost
    {
        int x,y,cost;
        muchie_cost(int a, int b, int c)
        {
            x=a;
            y=b;
            cost=c;
        }
        muchie_cost(){}
        bool operator < (const muchie_cost &m) const //operator pentru compararea costurilor a doua muchii
        {return cost < m.cost;}
    };

    int n; //nr de noduri
    int m; //nr de muchii
    vector<vector<int>> la; //vector cu listele de adiacenta
    vector<muchie_cost> vmc; //vector de muchii cu cost
    vector<vector<arc>> la_arce; //vector cu listele de adiacenta ale nodurilor dintr-un graf orientat(folosita pentru metodele Dijkstra si Bellman_Ford)
    bool tip; //variabila care ne spune daca graful este orientat sau nu(daca este orientat este true altfel este false)
    bool costuri;//variabila care ne spune daca muchiile grafului au sau nu asociate costuri(daca da costuri este true altfel este false)
    void dfs_mc(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result);//subprogram de tip dfs folosit de metoda Muchii_critice
    void dfs_bcx(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe); //subprogram de tip dfs folosit de metoda Biconexe
    void dfs_ctc(int x, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe);//subprogram de tip dfs folosit de metoda Componente_Tare_Conexe

public:
    Graf(int n, int m, bool tip, bool costuri);//constructor parametrizat care primeste si tipul grafului si daca muchiile au sau nu costuri: orientat(tip==true) sau neorientat(tip==false) si cu costuri pe muchii(costuri==true) sau fara(costuri==false)
    void Add_edge(int x, int y); //metoda de adaugare a unei muchii in graf
    void Add_edge_c(int x, int y, int c); //metoda de adaugare a unei muchii cu cost in graf
    void Add_arc(int x, int y, int d); //metoda de adaugare a unui arc cu distanta in graf
    void dfs(int x, vector<bool> &vizitat); //dfs = parcurgere dfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
    void bfs(int x, vector<bool> &vizitat);//bfs = parcurgere bfs ce pleaca din nodul x si afiseaza vectorul parcurgerii(primeste ca parametru si un vector in care marcheaza nodurile vizitate)
    void SortareTop(); //sortarea topologica a grafului(daca acesta este orientat si aciclic); afiseaza vectorul sortarii
    void Biconexe(); //metoda ce afiseaza vectorul de componente biconexe(care sunt vectori de noduri) ale grafului
    void Muchii_critice(); //metoda ce afiseaza vectorul de muchii critice(care sunt vectori cu 2 elemente) ale grafului
    void Componente_Tare_Conexe(); //metoda ce afiseaza vectorul de componente  tareconexe
    void Kruskal();//metoda ce implementeaza algoritmul lui Kruskal de determinare a APM-ului
    void Dijkstra(); //metoda ce implementeaza algoritmul lui Dijkstra de determinare a drumurilor minime de la un nod la toate celelalte


};


Graf::Graf(int n, int m, bool tip, bool costuri)
{
    this->n = n;
    this->m = m;
    this->tip = tip;
    this->costuri = costuri;
    la.resize(n+1);
    la_arce.resize(n+1);
}


void Graf::Add_edge(int x, int y)
{
    la[x].push_back(y);
    if(!tip)
        la[y].push_back(x);
}

void Graf::Add_edge_c(int x, int y, int c)
{
    vmc.push_back(muchie_cost(x,y,c));
}

void Graf::Add_arc(int x, int y, int d)
{
    la_arce[x].push_back(arc(y,d));
}


void Graf::dfs(int x, vector<bool> &vizitat)
{

    assert(vizitat.size()>=n);//verific daca vetorul dat ca parametru are dimensiunea corespunzatoare
    vizitat[x] = true;
    std::cout << x << " ";
    for(int i=0; i<la[x].size(); ++i)
    {
        int y = la[x][i];
        if (vizitat[y] == false)
            dfs(y, vizitat);
    }
}

void Graf::bfs(int x, vector<bool> &vizitat)
{
    assert(vizitat.size()>=n);//verific daca vetorul dat ca parametru are dimensiunea corespunzatoare
    queue<int> q;
    q.push(x);
    vizitat[x]=1;

    while(!q.empty())
    {
        x = q.front();
        std::cout << x << " ";
        q.pop();
        for(int i=0; i<la[x].size(); ++i)
        {
            int y=la[x][i];
            if(!vizitat[y])
            {
                q.push(y);
                vizitat[y]=true;
            }
        }
    }
}

void Graf::SortareTop()
{
    if(tip == false)
    { cout << "Metoda SortareTop este folosita doar la grafurile orientate aciclice!\n";
        return;
    }

    cout<< "Sortarea topologica a grafului dat este: ";

    //completam vector in care retinem gradele interioare ale nodurilor
    vector<int> gr_int(n+1);
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<la[i].size(); ++j)
            ++gr_int[la[i][j]];
    }

    queue<int> q; //coada folosita la sortarea topologica
    //parcurgem vectorul de grade si punem in coada nodurile cu gradul interior 0
    for(int i=1; i<=n; ++i)
        if(gr_int[i]==0)
            q.push(i);

    //parcurgem coada pentru a obtine o sortare topologica
    while(!q.empty())
    {
        int x;
        //extragem un nod din coada
        x = q.front();
        q.pop();
        //scadeam gradele interioare ale nodurilor in care intra nodul curent
        for(int i=0; i<la[x].size(); ++i)
        {
            int y = la[x][i];
            --gr_int[y];
            if(gr_int[y] == 0)
                q.push(y);
        }
        cout << x << " ";
    }

    cout << "\n(In cazul in care graful prezinta cicluri sortarea afisata este doar sortarea topologica a nodurilor ce nu fac parte din vreun ciclu)";
}

void Graf::dfs_bcx(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<muchie> &stiva, int &timp, vector<set<int>> &biconexe)
{

    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            stiva.push(muchie(x,z));//adaug muchia in stiva de muchii
            dfs_bcx(z, x, vizitat, moment, low, stiva, timp, biconexe);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];


            //determinare componente biconexe
            if(moment[x] <= low[z]) //deci x este punct critic
            {
                set<int> componenta;
                int a, b; //capetele unei muchii
                do
                {
                    muchie m=stiva.top();
                    stiva.pop();
                    a=m.x;
                    b=m.y;
                    componenta.insert(a);
                    componenta.insert(b);
                }while(a!=x || b!=z);
                biconexe.push_back(componenta);//adaug componenta in vectorul de componente biconexe
            }

        }
        else //am dat de o muchie de intoarcere
        {
            if(z!=parinte) //verific ca z sa nu fie parinte al lui x
            {    //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
                // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
                // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
                if (low[x] > moment[z])
                    low[x] = moment[z];
            }
        }
    }
}

void Graf::Biconexe()
{

    if(tip == true)
    { cout << "Metoda Biconexe este folosita doar la grafurile neorientate!\n";
        return;
    }

    vector<bool> vizitat(n+1); //vector vizitat
    vector<int> moment(n+1); //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    stack<muchie> stiva; //stiva in care vom retine muchiile unei componente biconeexe
    vector<set<int>> biconexe; //vectorul de componente biconexe

    int timp = 0;// timp = contor de timp pentru crearea vectorului moment

    //daca graful nu este conex, se analizeaza fiecare componenta conexa
    for(int i=1; i<=n; ++i)
        if(!vizitat[i])
            dfs_bcx(i,0,vizitat,moment,low,stiva, timp, biconexe);

    cout << "Numarul de componente biconexe: " << biconexe.size() << "\n";
    cout<< "Componentele biconexe sunt: \n";
    for(int i=0; i<biconexe.size(); ++i)
    {
        cout << i+1 << ") ";
        for(set<int>::iterator it=biconexe[i].begin(); it!=biconexe[i].end(); ++it)
            cout << *it << " ";
        cout << "\n";
    }
}

void Graf::dfs_mc(int x, int parinte, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, int &timp, vector<vector<int>> &result)
{
    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            dfs_mc(z, x, vizitat, moment, low, timp, result);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];


            //daca este muchie critica o adaugam in result
            if(low[z] > moment[x])
                result.push_back({x,z});

        }
        else //muchie de intoarcere
        {
            if(z!=parinte && low[x] > moment[z])
            {
                low[x] = moment[z];
            }
        }
    }
}

void Graf::Muchii_critice()
{
    if(tip == true)
    { cout << "Metoda Muchii_critice este folosita doar la grafurile neorientate!\n";
        return;
    }

    vector<bool> vizitat(n+1); //vector vizitat
    vector<int> moment(n+1); //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    vector<vector<int>> result; //vectorul de componente biconexe

    int timp = 0;// timp = contor de timp pentru crearea vectorului moment

    //daca graful nu este conex, se analizeaza fiecare componenta conexa
    for(int i=1; i<=n; ++i)
        if(!vizitat[i])
            dfs_mc(i,0,vizitat,moment,low, timp, result);


    cout << "Numarul de muchii critice: " << result.size() << "\n";
    cout << "Muchiile critice sunt: \n";
    for(int i=0; i<result.size(); ++i)
    {
        cout << i+1 << ") " << result[i][0] << " " << result[i][1] <<"\n";
    }
}

void Graf::dfs_ctc(int x, vector<bool> &vizitat, vector<int> &moment, vector<int> &low, stack<int> &stiva, set<int> &in_stack, int &timp, vector<set<int>> &tareconexe)
{
    vizitat[x] = 1;
    moment[x] = timp++;
    low[x] = moment[x]; //initiaizez low cu momentul curent(nu stiu momentan pana la ce nivel se poate intoarce)

    stiva.push(x);//adaug nodul in stiva de noduri si in multimea care tine evidenta nodurilor din stiva
    in_stack.insert(x);

    //parcurg lista de adiacente a lui x
    for(int i=0; i<la[x].size(); ++i)
    {
        int z = la[x][i];

        if (vizitat[z] == 0)
        {
            dfs_ctc(z, vizitat, moment, low, stiva, in_stack, timp, tareconexe);

            //daca z, care este fiu al lui x poate sa se intoarca mai sus decat x, atunci actualizez si low[x]
            // (pt ca x prin intermediul fiului, se va putea intoarce mai sus la randul sau)
            if(low[x] > low[z])
                low[x] = low[z];

        }
        else if(in_stack.find(z)!=in_stack.end())//am dat de o muchie de intoarcere si nodul z face parte din noua componenta tare_conexa
        {
            //daca z, care este fiu al lui x, are momentul mai mic decat x(a fost deja vizitat) si momentul sau este
            // strict mai mic decat momentul la care se poate intoarce x, atunci actualizez low[x]
            // (x prin intermediul lui z, al muchiei de inoarcere, se va intoarce mai sus)
            if (low[x] > moment[z])
                low[x] = moment[z];
        }
    }
    if(low[x]==moment[x]) //daca nodul e radacina in componenta tare_conexa curenta(am avut un circuit)
    {
        set<int> componenta;
        int y;
        do{
            y=stiva.top();
            stiva.pop();
            in_stack.erase(y);
            componenta.insert(y);
        }while(y!=x);
        tareconexe.push_back(componenta);
    }
}

void Graf::Componente_Tare_Conexe()
{
    if(tip == false)
    { cout << "Metoda Componente_Tare_Conexe este folosita doar la grafurile orientate!\n";
        return;
    }
    vector<bool> vizitat(n+1);
    vector<int> moment(n+1); //vector ce retine momentul  in care se viziteaza prima oara un nod di graf
    vector<int> low(n+1); //vector ce retine momentul cel mai mic al unui nod care poate fi atins de catre un descendent printr-o muchie de intoarcere
    stack<int> stiva; //stiva in care vom retine nodurile unei componente tare-conexe
    set<int> in_stack;//multimne care retine ce elemente sunt in stiva la un anumit moment
    vector<set<int>> tareconexe; //vectorul de componente tare-conexe
    int timp=0;

    //daca graful nu este conex, se analizeaza fiecare componenta tare-conexa
    for(int j=1; j<=n; ++j)
        if(vizitat[j]==0)
            dfs_ctc(j, vizitat, moment, low, stiva, in_stack, timp, tareconexe);

    cout << "Numarul de componente tareconexe: "<< tareconexe.size() << "\n";
    cout<< "Componentele tareconexe sunt: \n";
    for(int i=0; i<tareconexe.size(); ++i)
    {
        cout << i+1 << ") ";
        for(set<int>::iterator it=tareconexe[i].begin(); it!=tareconexe[i].end(); ++it)
            cout << *it << " ";
        cout << "\n";
    }

}

void Graf::Kruskal()
{
    if(tip == true)
    { cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile neorientate conexe!\n";
        return;
    }

    if(costuri == false)
    { cout << "Metoda Kruskal de determinare a APM-ului este folosita doar la grafurile ale caror muchii au asociate costuri!\n";
        return;
    }

    //sortam vectorul de muchii crescator dupa cost(in M*logM)
    sort(vmc.begin(), vmc.end());

    //definim o padure de multimi disjuncte
    DisjointSets dj(n);

    vector<muchie> rezultat;//vectorul in care vom retine muchiile APM-ului
    rezultat.resize(n-1);//APM-ul va avea exact n-1 muchii(pt ca este arbore)

    int contor = 0;//variabila care retine cate muchii au fost selectate pana la un anumit moment de timp
    int cost_total = 0;

    for(int i=0; i<m; ++i)
    {
        //obtin extremitatiile muchiei curente
        int x = vmc[i].x;
        int y = vmc[i].y;

        //aflu reprezentatntii lui x si y(pt a vedea daca sunt sau nu in multimi disjuncte)
        int rx = dj.Reprezentant(x);
        int ry = dj.Reprezentant(y);

        //au acelasi reprezentant muchia nu este buna si trec mai departe
        if(rx == ry)
            continue;

        //adaug muchia curenta in rezultat(in APM)
        rezultat[contor] = muchie(x,y);
        contor++;
        cost_total+=vmc[i].cost;

        //daca am atins numarul de muchii necesare APM-ului ne oprim
        if(contor == n-1)
            break;

        //reunim multimiile lui x si y
        dj.Reuniune(x,y);
    }
    //afisam rezultatul(APM-ul)
    cout << "\n";
    cout << "Costul total al APM-ului este: " << cost_total << "\n";
    cout << "Numarul de muchii din APM este: " << n-1 << "\n";
    cout << "Muchiile APM-ului sunt:\n";
    for(int i=0; i<contor; ++i)
        cout << rezultat[i].x << " " << rezultat[i].y << "\n";

}

void Graf::Dijkstra()
{
    //initializare
    vector<int> d(n+1, 1000000001); //vector de distante
    vector<int> t(n+1, 0); //vectorul de tati
    vector<int> selectat(n+1, 0); // vector ce retine daca un nod a fost selectat sau nu
    d[1] = 0;
    selectat[1] = 1;
    Min_heap H(n); //declaram heapul

    //punem in heap distantele de la nodul de start la toate nodurile sale adiacente si tatal acestor oduri(care este chiar nodul de start)
    for(int i=0; i<la_arce[1].size(); ++i)
    {
        H.push(la_arce[1][i]);
        d[la_arce[1][i].y] = la_arce[1][i].distanta;
        t[la_arce[1][i].y] = 1;
    }

    //in mod repetat, pentru restul de n-1 noduri, selectez nodurile adiacente(la fiecare pas este ales nodul cu distanta cea mai mica)
    //daca se poate ajunge in ele
    for(int k=0; k<n-1 && !H.empty(); ++k)
    {
        arc ac = H.pop(); //arcul curent

        selectat[ac.y] = 1;//marche ca selectat nodul curent

        for(int i=0; i<la_arce[ac.y].size(); ++i)
        {
            int z = la_arce[ac.y][i].y; //nodul in care s-a ajuns din  nodul curent
            if(selectat[z]==0) //daca vecinul nu a fost deja selectat
            {
                int nd = d[ac.y] + la_arce[ac.y][i].distanta;//noua distanta
                if(nd < d[z]) //relaxare muchie
                {
                    d[z] = nd;
                    t[z] = ac.y;
                    H.push(arc(z,nd));
                }
            }
        }
    }
    for(int i=2; i<=n; ++i)
        if(d[i] == 1000000001)
            fout << 0 << " ";
        else
            fout << d[i] << " ";

}


int main()
{
    int n, m, x, y, d;

    fin >> n >> m;
    Graf G(n,m, 1, 1);

    for(int i=0; i<m; ++i)
    {
        fin >> x >> y >> d;
        G.Add_arc(x, y, d);
    }

    G.Dijkstra();

    return 0;
}