#include<fstream>
#include<algorithm>
using namespace std;

typedef struct lol {
        int x,y,c;
}troll;

int i,n,m,rs,nr,arb[200005],b[200005];
troll a[400005];

int Find(int x) {
    int i,q;
    for(i=x;b[i]!=i;i=b[i]);

    for(;b[x]!=x) q=b[x],b[x]=i,x=q;
 return i;
}

void group(int x,int y) {
     b[Find(x)]=Find(y);
}

bool cmp(const troll &a,const troll &b) {
     return a.c<b.c;
}

int main()
{
  ifstream cin("apm.in");
  ofstream cout("apm.out");

  cin>>n>>m;
  for(i=1;i<=m;++i) cin>>a[i].x>>a[i].y>>a[i].c;

  sort(a+1,a+m+1,cmp);

  for(i=1;i<=n;++i) b[i]=i;

  for(i=1;i<=m;++i)
  if(Find(a[i].x)!=Find(a[i].y)) rs+=a[i].c,arb[++nr]=i,group(a[i].x,a[i].y);

  cout<<rs<<'\n'<<nr<<'\n';
  for(i=1;i<=nr;++i) cout<<a[arb[i]].x<<' '<<a[arb[i]].y<<'\n';

 return 0;
}