#include <iostream>
#include <fstream>
#define maxn 200005
using namespace std;
struct p{int x;int y;int c;}v[maxn],k[maxn];

int pozitie(int i,int j)
{int aux,mod=1;

while(i<j)
{if(v[i].c>v[j].c)
{aux=v[i].x;
v[i].x=v[j].x;
v[j].x=aux;

aux=v[i].y;
v[i].y=v[j].y;
v[j].y=aux;

aux=v[i].c;
v[i].c=v[j].c;
v[j].c=aux;
mod=1-mod;
}
 i=i+mod;
 j=j+mod-1;
}
    return i;
}

void divide(int i,int j)
{int k;
if(i<j)
{k=pozitie(i,j);
divide(i,k-1);
divide(k+1,j);
}
}

int main()



{int n,m,i,j,gr[maxn],sum=0,nr=0,a,b,h[maxn];
fstream f("apm.in",ios::in);
fstream g("apm.out",ios::out);
f>>n>>m;
for(i=1;i<=n;i++)
    {gr[i]=0;h[i]=0;}

for(i=1;i<=m;i++)
{f>>v[i].x>>v[i].y>>v[i].c;}

f.close();

divide(1,m);


sum=0;

i=1;
while(nr<n-1)
{
    //for(j=1;j<=n;j++)
//cout<<gr[j]<<" ";
//cout<<endl;

a=v[i].x;
b=v[i].y;
while(gr[a]!=0)
a=gr[a];
while(gr[b]!=0)
b=gr[b];

if(a!=b)
{   if(h[a]<h[b])
    {gr[a]=b;
    h[b]=h[b]+1;}
    else
    {gr[b]=a;
    h[a]=h[a]+1;}


nr++;
k[nr].x=v[i].x;
k[nr].y=v[i].y;
sum=sum+v[i].c;
}
else
    i++;


}

g<<sum<<'\n';
g<<nr<<'\n';
for(i=1;i<=nr;i++)
   g<<k[i].x<<" "<<k[i].y<<'\n';


g.close();




}