#include <iostream>
#include <fstream>

using namespace std;

class Graf
{
    unsigned long N, M;
    struct muchie {unsigned long nod1, nod2; short cost;};
    struct semi {unsigned long nod; short cost;};
    long cost;
    //vector <muchie> toate;
    muchie A[400001];
    semi  G[200000][200001];
public:
    Graf ();
    void citire();
    void prim (unsigned long r);
    void afisare ();
};

Graf::Graf ()
{
    int i;
    A[0].nod1=0;
    for (i=0; i<200000; i++)
        G[i][0].nod=0;
}

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

void Graf::prim(unsigned long r)
{
    semi v[N+3]; //first-nodul din arbore de care se leaga nodul i; second-costul
    unsigned long i, j, x, minim;
    short c;
    cost=0;
    muchie m;
    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;
    for (i=1; i<N; i++)
    {
        //in r avem ultimul nod ales
        for (j=1; j<=G[r][0].nod; j++)
        {
            x=G[r][j].nod;
            c=G[r][j].cost;
            if (c<v[x].cost && c!=-2000)
            {
                v[x].cost=c;
                v[x].nod=r;
            }
        }
        //am updatat vectorul
        minim=0;
        for (j=1; j<=N; j++)
        {
            if (v[j].cost<v[minim].cost && v[j].cost!=-2000)
            {
                minim=j;
            }
        }
        m.nod1=minim;
        m.nod2=v[minim].nod;
        m.cost=v[minim].cost;
        A[0].nod1++;
        A[A[0].nod1]=m;
        cost+=m.cost;
        v[minim].cost=-2000;
        r=minim;
    }
}

void Graf::citire()
{
    ifstream f ("apm.txt.txt");
    f>>N>>M;
    //muchie m;
    unsigned long i, x, y;
    short c;
    semi s;
    //G=new vector< semi > [N+3];
    for(i=0; i<M; i++)
    {
        //f>>m.x>>m.y>>m.c;
        f>>x>>y>>c;
        //toate.push_back(m);
        s.cost=c;
        s.nod=y;
        G[x][0].nod++;
        G[x][G[x][0].nod]=s;
        s.nod=x;
        G[y][0].nod++;
        G[y][G[y][0].nod]=s;
        //cout<<m.x<<' '<<G[m.x][G[m.x].size()-1].first<<' '<<G[m.x][G[m.x].size()-1].second<<'\n';
    }
}

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