#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

public:
    graf(const char*);
    void prim();
};

int main()
{
    graf ponderat1("apm.in");
    ponderat1.prim();
    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();
}

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;
}