#include <bits/stdc++.h>
using namespace std;

const int nm=1e5;
int p[nm+1];
int sz[nm+1];
struct muchie
{
    int x, y, c;
};
muchie v[nm+1], sol[nm+1];

int Find(int x)
{
    if(x==p[x])
    {
        return x;
    }
    return p[x]=Find(p[x]);
}

void Union(int x, int y)
{
    x=Find(x);
    y=Find(y);
    if(sz[x]< sz[y])
    {
        swap(x,y);
    }
    p[y]=x;
    sz[x] += sz[y];
    sz[y]= 0;
}
bool cmp( muchie a, muchie b)
{
    return a.c < b.c;
}

int main()
{
   ifstream cin("intrare apm.in");
   ofstream cout("intrare apm.out");
  int n, m;
  cin >> n >> m;
  for (int i=1; i<=n; i++)
  {
     p[i]=i;
     sz[i]=1;
  }
  
  for(int i=1; i<=m; i++)
  {
    cin >> v[i].x >> v[i].y >> v[i].c;
  }
  sort(v+1, v+m+1, cmp);
  int sum=0;
  int nr=0;
  for(int i=1; i<=m && nr<n-1; i++)
  {
      if(Find(v[i].x)!=Find(v[i].y))
      {
          nr++;
          sol[nr]=v[i];
          sum+=v[i].c;
          Union(v[i].x, v[i].y);
      }
  }
  cout << sum << '\n';
  cout << nr << '\n';
  for(int i=1; i<=nr; i++)
  {
      cout << sol[i].x << " " << sol[i].y << '\n';
  }
  
    return 0;
}