#include <iostream>
#include <fstream>

using namespace std;

class Graf
{
    unsigned long N, M;
    struct semi {unsigned long nod; short cost; semi *urm;};
    struct semimuchie {unsigned long nod; short cost;};
    long cost;
    int tati[201];
    semi * G[201];
    void push (unsigned long unde, unsigned long nod, short C);
public:
    Graf ();
    void citire();
    void prim (unsigned long r);
    void afisare ();
    ~Graf ();
};

Graf::Graf ()
{
    unsigned long i;
    for (i=1; i<=200; i++)
        G[i]=NULL;
}

Graf::~Graf()
{
    unsigned long i;
    semi *aux;
    for (i=1; i<=N; i++)
    {
        while (G[i]!=NULL)
        {
            aux=G[i]->urm;
            delete G[i];
            G[i]=aux;
        }
    }
}

void Graf::push(unsigned long unde, unsigned long nod, short C)
{
    semi *s;
    s=new semi;
    s->cost=C;
    s->nod=nod;
    s->urm=G[unde];
    G[unde]=s;
}

void Graf::prim(unsigned long r)
{
    semimuchie v[N+1]; //nodul din arbore de care se leaga nodul i si costul
    unsigned long i, x, k, minim;
    semi *j;
    short c;
    cost=0;
    for (i=0; i<=N; i++)
    {
        v[i].cost=2000;
    }
    v[r].cost=-2000;//un nod are costul -2000 daca apartine arborelui
    v[r].nod=0;
    tati[r]=0;
    for (i=1; i<N; i++)//avem de ales N-1 muchii
    {
        //in r avem ultimul nod ales
        for (j=G[r]; j!=NULL; j=j->urm)
        {
            x=j->nod;
            c=j->cost;
            if (c<v[x].cost && c!=-2000)
            {
                v[x].cost=c;
                v[x].nod=r;
            }
        }
        //am updatat vectorul
        minim=0;
        for (k=1; k<=N; k++)
        {
            if (v[k].cost<v[minim].cost && v[k].cost!=-2000)
            {
                minim=k;
            }
        }
        tati[minim]=v[minim].nod;
        cost+=v[minim].cost;
        v[minim].cost=-2000;
        r=minim;
    }
}

void Graf::citire()
{
    ifstream f ("apm.txt.txt");
    f>>N>>M;
    unsigned long i, x, y;
    short c;
    for(i=0; i<M; i++)
    {
        f>>x>>y>>c;
        push (x, y, c);
        push (y, x, c);
    }
}

void Graf::afisare()
{
    ofstream f ("afis.txt");
    f<<cost<<'\n'<<N-1<<'\n';
    unsigned long i;
    for (i=2; i<=N; i++)
    {
        f<<i<<' '<<tati[i]<<'\n';
    }
}

int main()
{
    Graf G;
    G.citire();
    G.prim(1);
    G.afisare();
    return 0;
}