#include <stdio.h>
#include <algorithm>
using namespace std;
FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");
int k,t[200005],h[200005],i,n,m,sum=0;
struct mch{
int x,y,ct;
}u[400005];
struct da{
int x,y;
}sol[400005];
int comp(mch a,mch b){
return a.ct<b.ct;

}
int uni(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];
if(r1==r2) return 0;
while(t[x]!=r1){x1=t[x];t[x]=r1;x=x1;}
while(t[y]!=r2){y1=t[y];t[y]=r2;y=y1;}
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;
}
void kruskal(){
k=0;

int i=1;
while(k<n-1){
 if(uni(u[i].x,u[i].y)){
    sum+=u[i].ct;
    k++;
    sol[k].x=u[i].x;
    sol[k].y=u[i].y;
 }

    i++;
}
}
int main()
{fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)

fscanf(f,"%d%d%d",&u[i].x,&u[i].y,&u[i].ct);

for(i=1;i<=n;i++)t[i]=i,h[i]=1;
sort(u+1,u+m+1,comp);
kruskal();
fprintf(g,"%d\n%d\n",sum,k);
for(i=1;i<=k;i++)fprintf(g,"%d %d\n",sol[i].x,sol[i].y);
fclose(f);
fclose(g);

    return 0;
}