#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
struct muchie{int a,b,c;};
muchie v[400000];
int t[400000],r[400000];
void sort(int l,int d)
{int st,dr;
int m;
st=l;
dr=d;
m=v[(st+dr)/2].c;
while(st<=dr)
{while(v[st].c<m)
st++;
while(v[dr].c>m)
dr--;
if(st<=dr)
{swap(v[st],v[dr]);
st++;
dr--;}}
if(l<dr)
sort(l,dr);
if(st<d)
sort(st,d);}
int main()
{ifstream f("apm.in");
ofstream h("apm.out");
int m,n,i,x,y,k=0,cc=0;
vector<int> vv;
f>>n>>m;
for(i=1;i<=m;i++)
f>>v[i].a>>v[i].b>>v[i].c;
for(i=1;i<=n;i++)
{t[i]=i;
r[i]=1;}
sort(1,m);
for(i=1;i<=m;i++)
{x=v[i].a;	
while(t[x]!=x)
x=t[x];
y=v[i].b;
while(t[y]!=y)
y=t[y];
if(y!=x)
{cc=cc+v[i].c;
vv.push_back(v[i].a);
vv.push_back(v[i].b);
k++;
if(r[x]>r[y])
t[y]=x;
else
if(r[x]<r[y])
t[x]=y;
else
{t[x]=y;
r[y]++;}}
if(k==n-1)
break;}
h<<cc<<'\n';
h<<vv.size()/2<<'\n';
for(i=0;i<vv.size();i++)
{h<<vv[i]<<' '<<vv[i+1]<<'\n';
i++;}
return 0;}