#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,k[200001],p,r,l;
struct muchie
{ int x,y,c;
}a[400001];
bool cmp(muchie a,muchie b)
{ return a.c<b.c;
}
vector < pair <int,int> > v;
int main()
{ in>>n>>m;
  for(int i=1;i<=m;i++)
    in>>a[i].x>>a[i].y>>a[i].c;
  sort(a+1,a+m+1,cmp);
  for(int i=1;i<=n;i++)
    k[i]=i;
  for(int i=1;i<=m;i++)
  { if(k[a[i].x]!=k[a[i].y])
    { p=k[a[i].y];
      for(int j=1;j<=m;j++)
        if(k[j]==p)
           k[j]=k[a[i].x];
      r+=a[i].c;
      l++;
      v.push_back(make_pair(a[i].x,a[i].y));
    }
  }
  out<<r<<'\n'<<l<<'\n';
  for(int i=1;i<=n;i++)
    k[i]=i;
  for(int i=0;i<l;i++)
    out<<v[i].first<<' '<<v[i].second<<'\n';
  in.close();
  out.close();
  return 0;
}