#include <stdio.h>
#include <algorithm>
using namespace std;

int much[400000][3], pa[400000], sef[200000]; //nr[200000];
bool mark[400000];

int gasi(int x){
  if(sef[x]==x)
    return x;
  return sef[x]=gasi(sef[x]);
}

inline void unes(int x, int y){
  int x1=gasi(x), y1=gasi(y);
  //if(nr[x1]>nr[y1])
    //swap(x1,y1);
  sef[x1]=y1;
  //nr[y1]+=nr[x1];
  //nr[x1]=0;
}

bool cmp(int x, int y){
  return much[x][2]<much[y][2];
}

int main()
{
  FILE *fi=fopen("apm.in", "r"), *fo=fopen("apm.out", "w");
  int n, m, i, S, k;
  fscanf(fi, "%d%d", &n, &m);
  for(i=0;i<m;i++){
    for(int j=0;j<3;j++)
      fscanf(fi, "%d", &much[i][j]);
    pa[i]=i;
  }
  for(i=0;i<n;i++)
    sef[i]=i;//nr[i]=1;
  sort(pa,pa+m,cmp);
  S=0;
  k=0;
  for(i=0;i<m;i++)
    if(gasi(much[pa[i]][0])!=gasi(much[pa[i]][1])){
      S+=much[pa[i]][2];
      unes(much[pa[i]][0],much[pa[i]][1]);
      mark[pa[i]]=true;
      k++;
    }
  fprintf(fo, "%d\n%d\n", S, k);
  for(i=0;i<m;i++)
    if(mark[i])
      fprintf(fo, "%d %d\n", much[i][0], much[i][1]);
  fclose(fi);
  fclose(fo);
  return 0;
}