#include <fstream>
#include <algorithm>
#define N 200000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,j,k,V[N],aux,nr,c;
struct muchie{
    int start,stop,cost;
}M[2*N],M2[2*N];
bool fcost(muchie a, muchie b){
    return a.cost<b.cost;
}

int main(){
    fin>>n>>m;
    aux=m;
    while(aux)
    {
        aux--;
        fin>>i>>j>>k;
        M[m-aux].start=i;
        M[m-aux].stop=j;
        M[m-aux].cost=k;
    }
    for(i=1;i<=n;i++)
        V[i]=i;
    sort(M+1,M+m+1,fcost);
    for(i=1;i<=m;i++)
    {
        if(V[M[i].start]!=V[M[i].stop])
        {
            nr++;
            M2[nr].start=M[i].start;
            M2[nr].stop=M[i].stop;
            c+=M[i].cost;
            k=min(V[M[i].start],V[M[i].stop]);
            j=max(V[M[i].start],V[M[i].stop]);
            for(aux=1;aux<=n;aux++)
                if(V[aux]==j)
                    V[aux]=k;
        }
    }
    fout<<c<<'\n'<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        fout<<M2[i].start<<" "<<M2[i].stop<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}