#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,S,tata[251],h[251];
priority_queue < pair <int,int>, vector < pair <int,int> >, greater < pair <int,int> > > Q;

struct muchie
{
    int x,y,cost;
} v[10010],sol[210];

int compare(muchie A,muchie B)
{
    return(A.cost<B.cost);
}

int TATA(int nod)
{
    while(nod!=tata[nod])
    {
        nod=tata[nod];
    }

    return nod;
}

int ck_muchie(int nod1,int nod2)
{
    int r1,r2;

    r1=TATA(nod1);
    r2=TATA(nod2);

    if(r1==r2)return 0;
    if(h[r1]>h[r2])tata[r2]=r1;
    else if(h[r2]>h[r1])tata[r1]=r2;
    else
    {
        tata[r2]=r1;
        h[r1]++;
    }

    return 1;
}

void kruskal()
{
    int k,indice,nod1,nod2,muchie_cost;

    k=0;
    while(k<n-1)
    {
        indice = Q.top().second;
        Q.pop();

        muchie_cost=v[indice].cost;
        nod1=v[indice].x;
        nod2=v[indice].y;

        if(ck_muchie(nod1,nod2))
        {
            k++;
            sol[k].x=nod1;
            sol[k].y=nod2;
            sol[k].cost=muchie_cost;
            S+=muchie_cost;
        }
    }
}

int m,i,T,pas,nod1,nod2,muchie_cost;
int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>v[i].x>>v[i].y>>v[i].cost;
        Q.push({v[i].cost,i});
    }

    for(i=1; i<=n; i++)
    {
        tata[i]=i;
        h[i]=1;
    }

    kruskal();
    g<<S<<'\n';

    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<'\n';
    }

   /* while(!Q.empty())Q.pop();


    f>>T;
    for(pas=1; pas<=T; pas++)
    {
        f>>nod1>>nod2>>muchie_cost;

        v[n].x=nod1;
        v[n].y=nod2;
        v[n].cost=muchie_cost;

        Q.push({v[n].cost,n});

        for(i=1; i<=n; i++)
        {
            tata[i]=i;
            h[i]=1;
            if(i<n)
            {
                v[i].x=sol[i].x;
                v[i].y=sol[i].y;
                v[i].cost=sol[i].cost;
                Q.push({v[i].cost,i});
            }
        }

        S=0;
        kruskal();

        if(!Q.empty())Q.pop(); // in coada erau n elemente si eu la drum folosesc n-1 => eventual mai ramane un elemente => mai dau un pop() ca sa o golesc

        g<<S<<'\n';
    }
*/
    return 0;
}