#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct gf{
    int v1,v2,cost;
}*vect;
int tata_nod(int tt[200000],int x)
{
    if (tt[x]==x) return x;
    int tt_nou=tata_nod(tt,tt[x]);
    tt[x]=tt_nou;
    return tt_nou;
}
bool comp(gf a,gf b)
{
    return a.cost<b.cost;
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m,*v_tati,*h,cst=0,*viz;
    fin>>n>>m;
    vect= new gf[m];
    v_tati= new int[n];
    viz= new int[m];
    h= new int[n];
    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;
    sort(vect,vect+m,comp);
    for(int i=1; i<=n; i++)
       {
        v_tati[i]=i;
        h[i]=1;
       }
    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)
        {
            if(h[tata_v1]>h[tata_v2])
            {
                v_tati[tata_v2]=tata_v1;
                h[tata_v1]+=h[tata_v2];
            }else
            {
                v_tati[tata_v1]=tata_v2;
                h[tata_v2]+=h[tata_v1];
            }
            viz[i]=1;
            cst+=vect[i].cost;
        }
    }
    fout<<cst<<'\n';
    fout<<n-1<<'\n';
    for(int i=0; i<m; i++)
        if(viz[i]==1) fout<<vect[i].v1<<' '<<vect[i].v2<<'\n';
    return 0;
}