#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
struct gf{
    int v1,v2,cost;
}vect[400000];
int tata_nod(int tt[200000],int x)
{
   while (x!=tt[x]) x=tt[x];
   return x;
}
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[200000],cst=0,viz[200000];
    fin>>n>>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;
}