//Kruskal cu cele  multimi de paduri disjuncte
// si cele 2 optimizari - 100p

#include <cstdio>
#include <algorithm>
using namespace std;

struct muchie{int x,y,c;};
int n,m,i,t[200001],h[200001],k,cost,sol[200000];
muchie a[400001];

int compare(muchie x,muchie y)
{
 return x.c<y.c;
}

int muchie(int x,int y)
{int r1,r2,x1,y1,c;
r1=x;r2=y;
while (r1!=t[r1]) r1=t[r1];
while (r2!=t[r2]) r2=t[r2];

//regula de compresie
while (t[x]!=r1) {x1=t[x];t[x]=t[x1];x=x1;}
while (t[y]!=r2) {y1=t[y];t[y]=t[y1];y=y1;}

if (r1==r2) return 0;

//unfica subarborii de radacini r1 si r2
if (h[r1]>h[r2]) {t[r2]=r1;c=r1;}
else {t[r1]=r2;c=r2;}
if (h[r1]==h[r2]) h[c]++;

return 1;
}

int main()
{FILE *f1 = fopen("apm.in","r");
FILE *f2 = fopen("apm.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d%d",&a[i].x,&a[i].y,&a[i].c);}
sort(a+1,a+m+1,compare);
for (i=1;i<=n;i++) {t[i]=i;h[i]=1;}
k=0;

i=1;
while (k<n-1)
{if (muchie(a[i].x,a[i].y))
   {cost+=a[i].c;sol[++k]=i;}
i++;
}
fprintf(f2,"%d\n%d\n",cost,n-1);
for (i=1;i<=n-1;i++) fprintf(f2,"%d %d\n",a[sol[i]].x,a[sol[i]].y);

fclose(f1);
fclose(f2);
return 0;
}