#include <iostream>
#include <fstream>
#define MAXIM 2000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,n1[400000],n2[400000],cost[400000],viz[200000],ma,k=1;
int taie(int i,int j)
{ int ii=0,jj=-1,aux;
while(i<j)
{if(cost[i]>cost[j])
{	aux=cost[i];cost[i]=cost[j];cost[j]=aux;
    aux=n1[i];n1[i]=n1[j];n1[j]=aux;
    aux=n2[i];n2[i]=n2[j];n2[j]=aux;
    aux=ii;   ii=-jj; jj=-aux;}
i=i+ii;
j=j+jj;
} return i;
}
void QS(int li, int ls)
{ if(li<ls)
	{int p;
p=taie(li,ls);
QS(li,p-1);
QS(p+1,ls);}}
void APM()
{ int i,j,mini,a,a1;


 for(i=1;i<=m;i++)
       {      if((viz[n1[i]]==0)&&(viz[n2[i]]==0))
               {viz[n1[i]]=n1[i];
               viz[n2[i]]=n1[i];  ma=ma+cost[i];k++;}
                else if((viz[n1[i]]==0)||(viz[n2[i]]==0))
                {viz[n1[i]]=viz[n2[i]]=viz[n1[i]]+viz[n2[i]];
                 ma=ma+cost[i];k++;}
               else {
                    if(viz[n1[i]]!=viz[n2[i]]){for(j=1;j<=n;j++)if(viz[j]==viz[n1[i]]&&j!=n1[i])viz[j]=viz[n2[i]];
                                   viz[n1[i]]=viz[n2[i]]; ma+=cost[i];k++;} else {n1[i]=n2[i]=0;}
            }
}

}
int main()
{ int a,b,c,i;
in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>a>>b>>c;
    n1[i]=a;
    n2[i]=b;
    cost[i]=c;
    }
QS(1,m);;

in.close();
APM();
out<<ma<<"\n";
out<<k-1<<"\n";
for(i=1;i<=m;i++)
    if(n1[i]!=0)out<<n1[i]<<" "<<n2[i]<<"\n";
    out.close();
        return 0;
}