#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct arbore{
  int t,s;
};
const int N=200005;
const int M=400005;
arbore pad[N];
struct muchii{
  int val,x,y;
} mc[M];
muchii sol[M];
int n,m;
bool cmp(muchii a,muchii b){
  return a.val<b.val;
}
int findtata(int p){
  if(pad[p].t==p)
    return p;
  pad[p].t=findtata(pad[p].t);
  return pad[p].t;
}
void uneste(int a,int b){
  int atat=findtata(a);
  int btat=findtata(b);
  if(pad[atat].s>pad[btat].s){
    pad[btat].t=atat;
  }
  else if(pad[btat].s>pad[atat].s){
    pad[atat].t=btat;
  }
  else{
    pad[btat].t=atat;
    pad[atat].s++;
  }
}
int main()
{
    FILE*fin,*fout;
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    int n,m;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=m;i++){
      fscanf(fin,"%d %d %d",&mc[i].x,&mc[i].y,&mc[i].val);
    }
    sort(mc+1,mc+m+1,cmp);
    for(int i=1;i<=n;i++){
      pad[i]={i,1};
    }
    int nrsol=0,solo=0;
    for(int i=1;i<=m;i++){
      int xtata=findtata(mc[i].x),ytata=findtata(mc[i].y);
      if(xtata!=ytata){
        solo+=mc[i].val;
        sol[++nrsol]=mc[i];
        uneste(mc[i].x,mc[i].y);
      }
    }
    fprintf(fout,"%d\n%d\n",solo,nrsol);
    for(int i=1;i<=nrsol;i++){
      fprintf(fout,"%d %d\n",sol[i].x,sol[i].y);
    }
    return 0;
}