#include <fstream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{int x,y,v;};
muchie a[400001];
bool cmp(muchie a,muchie b)
{
  return a.v<b.v;
}
int n,m,i,j,sol,r[100001],ms[100001],nrm,p[100001];
int findset(int x)
{
  while (p[x]!=x)
    x=p[x];
  return x;
}
void Union(int x,int y)
{
  if (r[x]>r[y])
    p[y]=x;
  else
  {
    p[x]=y;
    if (r[x]==r[y])
      r[y]++;
  }
}
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
      f>>a[i].x>>a[i].y>>a[i].v;
   for (i=1;i<=n;i++)
    p[i]=i;
    sort(a+1,a+m+1,cmp);
  for (i=1;i<=m;i++)
       if (findset(a[i].y)!=findset(a[i].x))
        Union(findset(a[i].y),findset(a[i].x)),ms[++nrm]=i,sol+=a[i].v;
    g<<sol<<'\n';
    g<<nrm<<'\n';
    for (i=1;i<=nrm;i++)
      g<<a[ms[i]].y<<' '<<a[ms[i]].x<<'\n';
    return 0;
}