#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
struct gf{
    int v1,v2,cost;
}*vect;
int tata_nod(int *tt,int x)
{
    if (tt[x]==x) return x;
    int tt_nou=tata_nod(tt,tt[x]);
    tt[x]=tt_nou;
    return tt_nou;
}
int comp(const void *a,const void *b)
{
    gf *A=(gf*)a;
    gf *B=(gf*)b;
    return (A->cost)-(B->cost);
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m,*v_tati,cst=0,*viz;
    fin>>n>>m;
    vect= new gf[m];
    v_tati= new int[n];
    viz=new int[m];
    for (int i=0; i<m; i++)
        viz[i]=0;
    for (int i=0; i<m; i++)
        fin>>vect[i].v1>>vect[i].v2>>vect[i].cost;
    qsort(vect,m,sizeof(gf),comp);
    for(int i=1; i<=n; i++)
        v_tati[i]=i;
    for(int i=0; i<m; i++)
    {
        int tata_v1,tata_v2;
        tata_v1=tata_nod(v_tati,vect[i].v1);
        tata_v2=tata_nod(v_tati,vect[i].v2);
        if(tata_v1!=tata_v2)
        {
            viz[i]=1;
            v_tati[tata_v1]=tata_v2;
            cst+=vect[i].cost;
        }
    }
    fout<<cst<<endl;
    fout<<n-1<<endl;
    for(int i=0; i<m; i++)
        if(viz[i]==1)
            fout<<vect[i].v1<<' '<<vect[i].v2<<endl;
    return 0;
}