#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{
    int a,b,c;
};
muchie M[200000];
bool criteriu(muchie A, muchie B) {return A.c<B.c;}
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;


 for(i=1;i<=m;i++)
       {      if(viz[M[i].a]==0&&viz[M[i].b]==0)
                        {   viz[M[i].a]=viz[M[i].b]=M[i].a;  ma+=M[i].c;k++;}
              else
                    if(viz[M[i].a]==0||viz[M[i].b]==0)
                {viz[M[i].a]=viz[M[i].b]=viz[M[i].a]+viz[M[i].b];
                 ma+=M[i].c;k++;}
              else {
                   if(viz[M[i].a]!=viz[M[i].b]){for(j=1;j<=n;j++)if(viz[j]==viz[M[i].a]&&j!=M[i].a)viz[j]=viz[M[i].b];
                                   viz[M[i].a]=viz[M[i].b]; ma+=M[i].c;k++;}
              else {M[i].a=M[i].b=0;}
            }
}

}
int main()
{ int a,b,c,i;
in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>a>>b>>c;
    M[i].a=a;
    M[i].b=b;
    M[i].c=c;
    }
//QS(1,m);
sort(M+1,M+m+1,criteriu);
in.close();
APM();
out<<ma<<"\n";
out<<k-1<<"\n";
for(i=1;i<=m;i++)
    if(M[i].a!=0)out<<M[i].a<<" "<<M[i].b<<"\n";
    out.close();
        return 0;
}