#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>

using namespace std;

class graf
{
    int iNodes,iEdges,iMax,iCost;
    vector< vector<int> > vGraf;

public:
    graf(const char*);
    ~graf();

    void show() const;
    void prim();
    void dijkstra() const;// Va calcula distanta minima dintre nodul 1 si toate celelate noduri

};

int main()
{
    graf ponderat1("graf.in"),ponderat2("graf2.in");
    //ponderat.show();
    ponderat1.prim();
    system("pause");
    ponderat2.prim();
    system("cls");
    ponderat2.dijkstra();
    return 0;
}

graf::graf(const char* FILE)
{
    ifstream f(FILE);
    f>>iNodes>>iEdges;
    vGraf.resize(iNodes+1);
    for(unsigned i=1; i <= iNodes; i++)
        vGraf[i].resize(iNodes+1);
    for(unsigned i=0; i < iEdges; i++)
    {
        int x,y,pond;
        f>>x>>y>>pond;
        static int max = pond;
        if(max < pond) max = pond;
        iMax = max;
        vGraf[x][y] = pond;
        vGraf[y][x] = pond;
    }
    f.close();
}

graf::~graf()
{
}

void graf::show() const
{
    for(unsigned i=1; i <= iNodes; i++)
    {
        for(unsigned j=1; j <= iNodes; j++)
        {
            cout<<vGraf[i][j]<<" ";
        }
        cout<<endl;
    }
}

void  graf::prim()
{
    vector <int> parc;
    parc.resize(2*iNodes);
    bool bNodes[iNodes+1];
    int iCost = 0;
//Incepem din nodul 1
    bNodes[1] = true;
    for(unsigned i = 1; i < iNodes; i++) //Adaugarea toturor nodurilor
    {
        int iMin = iMax; //De revenit
        int x,y;
        for(unsigned j = 1; j <= iNodes; j++)
        {
            if(bNodes[j])
            {
                for(unsigned k = 1; k <= iNodes; k++)
                {
                    if(vGraf[j][k] < iMin && !bNodes[k] && vGraf[j][k])
                    {
                        iMin = vGraf[j][k];
                        x = j;
                        y = k;
                    }
                }
            }
        }
        parc[2*i-1] = x;
        parc[2*i] = y;
        iCost += iMin;
        bNodes[y] = true;
    }
    cout<<iCost<<endl;
    for(unsigned i = 1; i < iNodes; i++)
        cout<<parc[2*i-1]<<" "<<parc[2*i]<<endl;
    graf::iCost = iCost;
}

void graf::dijkstra() const
{
    vector <int> parc;
    parc.resize(iNodes-1);
    for(unsigned i=0;i < iNodes-1;i++)
        parc[i] = iCost;
    for(unsigned j=1;j <= iNodes;j++)
    {
        int dist;
        if(j == 1)
            dist = 0;
        else
            dist = parc[j-2];
        for(unsigned i=0;i < iNodes-1;i++)
        {
            if(vGraf[j][i+2] && vGraf[j][i+2] + dist < parc[i])
                parc[i] = vGraf[j][i+2] + dist;
        }
    }

    for(unsigned i=0;i < iNodes-1;i++)
        cout<<parc[i]<<" ";
}