#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,cx[200005],ord[200005],sum,k;

struct coord
{
    int x;
    int y;
    int d;
} v[400005];

int arbi(int i)
{
    if (cx[i]==i) return i;
    else return cx[i]=arbi(cx[i]);
}

bool mic(coord a, coord b)
{
    if (a.d<b.d) return 1;
        else return 0;
}

int main()
{int i;

f>>n>>m;
for (i=1; i<=m; i++)
  f>>v[i].x>>v[i].y>>v[i].d;

for (i=1; i<=n; i++) cx[i]=i;
sort(v+1,v+m+1,mic);

/*for (i=1; i<=m; i++)
{
  if (cx[v[i].x]!=cx[v[i].y])
  {
      k++;
      sum+=v[i].d;
      int aux=cx[v[i].x];
      int aux1=cx[v[i].y];
      for (j=1; j<=n; j++)
        if (cx[j]==aux) cx[j]=aux1; //cx[v[i].y];
      v[i].x = -v[i].x;
  }
  if (k==n-1) break;
} */
for (i=1; i<=m; i++)
{
  if (arbi(v[i].x)!=arbi(v[i].y))
  {
      sum+=v[i].d;
      cx[arbi(v[i].x)]=v[i].y;
      k++;
      ord[k]=i;
  }
}
g<<sum<<"\n";
g<<k<<"\n";
for (i=1; i<=k; i++)
  g<<v[ord[i]].x<<" "<<v[ord[i]].y<<"\n";
    return 0;
}