#include <iostream>
#include <fstream>

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

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

int n,m,a[2000][2000],cx[2000],sum,k;

int main()
{int i,j;

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;

for (i=1; i<=m-1; i++)
    for (j=i; j<=m; j++)
      if (v[i].d>v[j].d)
          swap(v[i],v[j]);

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