#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],a,b,d,sum=0,nr=0;
fstream f("apm.in",ios::in);
fstream g("apm.out",ios::out);
f>>n>>m;
for(i=1;i<=n;i++)
    gr[i]=i;
for(i=1;i<=m;i++)
{f>>v[i].x>>v[i].y>>v[i].c;
sum=sum+v[i].c;
gr[v[i].x]++;
gr[v[i].y]++;}

f.close();

divide(1,m);

sum=0;


for(i=1;((i<=m)&&(nr<n-1));i++)
{if(gr[v[i].x]!=gr[v[i].y])
{sum=sum+v[i].c;
gr[v[i].x]=gr[v[i].y];
nr++;
k[nr].x=v[i].x;
k[nr].y=v[i].y;
}}


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


g.close();




}