#include <stdio.h>
#include <vector>
#include <set>

#define mp make_pair

using namespace std;

struct nod{
int x;
int y;
}sol1[200008];

multiset < pair < int, pair < int, int> > > H;
multiset < pair < int, pair < int, int> > >::iterator it;


int c[200008],r[200008],n,m,i,x,y,z,nrm,nr,sum,x1,x2;

int caut(int k){
if (k!=c[k])caut(c[k]);
else return c[k];
}

void bifez(int x,int y){
if (r[x]>r[y])c[y]=x;
else c[x]=y;
if(r[x]==r[y])r[y]++;
}


int main()
{
freopen("apm.in"," r",stdin);
freopen("apm.out"," w",stdout);

scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){c[i]=i;r[i]=1;}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
H.insert(mp(z,mp(x,y)));
}
nr=0;
sum=0;
for(it=H.begin();it!=H.end();++it){
x1=caut((*it).second.first);
x2=caut((*it).second.second);

if(x1!=x2){
sum+=(*it).first;
sol1[++nr].x=x1;
sol1[nr].y=x2;
bifez(x1,x2);
}
}
printf("%d\n",sum);
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%d %d\n",sol1[i].x,sol1[i].y);



return 0;
}