# include <stdio.h>
# define nmax 801
# define mmax 1501
# define inf 1001
struct muchie{
	int x,y;
}m[mmax];
int N,M,G[nmax][nmax],S[nmax],A[nmax];
long C[nmax];
int main(){
  int i,j,k=0,x,y,ct,ok;
  long CT,Min;
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  scanf("%d %d",&N,&M);
  for (i=1;i<=N;++i)
    for (j=1;j<=N;++j)
	     G[i][j]=inf;
  for (i=1;i<=M;++i){
    scanf("%d %d %d",&x,&y,&ct);
    G[x][y]=ct; G[y][x]=ct;
//    G[x][0]++; G[x][G[x][0]]=ct;
//    G[y][0]++; G[y][G[y][0]]=ct;
  }
  for (i=2;i<=N;i++) S[i]=A[i]=1,C[i]=G[1][i];
  CT=0;
  do{
	Min=100000;  ok=1;
	for (i=2;i<=N;i++)
		if (C[i]<Min && A[i]){
			Min=C[i];
			x=i;ok=0;
		}
	if (!ok) {
	  k++;m[k].x=x;m[k].y=S[x];
	  CT+=G[x][S[x]]; A[x]=0;
	  for (i=2;i<=N;i++)
	    if (A[i] && C[i]>G[x][i]){
			S[i]=x;
			C[i]=G[x][i];
		}
	    }
  }while (!ok);
  printf("%ld\n",CT);
  printf("%d\n",k);
  for (i=1;i<=k;i++)
     printf("%d %d\n",m[i].x,m[i].y);
  return 0;
}