#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
bitset <200000> viz;
struct gf{
    int v1,v2,cost;
}vect[400000];
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[200000],cst=0;
    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;
    sort(vect,vect+m,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;
}