#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 1001
using namespace std;


struct muchie {
    long x, y, cost;
};

bool compar (muchie a, muchie b) {
      if (a.cost<b.cost) return true;
      return false;       
}
muchie muq[NMAX];
char gmuq[NMAX];
long comp[NMAX];

int main(void) {
    FILE * fi = fopen("apm.in","rt");
    FILE * fo = fopen("apm.out","wt");
    
    long n, m;
    fscanf(fi,"%ld %ld",&n,&m);
    for (long i=0; i<m; i++) {
        fscanf(fi,"%ld %ld %ld",&muq[i].x,&muq[i].y,&muq[i].cost);
    }
    sort(&muq[0],&muq[m],compar);
//    for (long i=0; i<m; i++) fprintf(fo,"muchia %ld %ld @%ld\n",muq[i].x,muq[i].y,muq[i].cost);
    for (long i=1; i<=n; i++)
        comp[i]=i;
    for (long i=0; i<m; i++) {
        if (comp[muq[i].x]!=comp[muq[i].y]) {
//           fprintf(fo,"am ales muchia %ld %ld; compurile extremelor sunt %ld %ld\n",muq[i].x,muq[i].y,comp[muq[i].x],comp[muq[i].y]);
//           fprintf(fo,"apdatez toate alea cu componenta %ld\n",comp[muq[i].y]);
           long serci = comp[muq[i].y];
           for (long j=1; j<=n; j++) if (comp[j]==serci) {
               comp[j]=comp[muq[i].x];
//               fprintf(fo,"apdatat %ld cu comp: %ld \n",j,comp[j]);
           } else {
//              fprintf(fo,"n-am apdatat %ld (pentru ca are comp: %ld).\n",j,comp[j]);
           }
           gmuq[i]=1;
        }
    }
    
    long costt=0; long cnt=0;
    for (long i=0; i<m; i++) if (gmuq[i]) { costt+=muq[i].cost; cnt++; }
    fprintf(fo,"%ld\n%ld\n",costt,cnt);
    for (long i=0; i<m; i++) if (gmuq[i]) fprintf(fo,"%ld %ld\n",muq[i].x,muq[i].y);
    
    fclose(fi); fclose(fo);
    return 0;  
};