#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 200005;
const int MMAX = 400005;
struct ABC
{
  int x, y;
  int cost;
};
struct SOLUTIE
{
  int x, y;
};
SOLUTIE sol[NMAX];
ABC v[MMAX];
int t[NMAX];
int h[NMAX];
bool cmp(ABC first, ABC second)
{
  return first.cost < second.cost;
}
int FindSet(int x)
{
  if(t[x] == x)
    return x;
  return FindSet(t[x]);
}
void UnionSet(int x, int y)
{
  if(h[x] == h[y]) {
    ++h[x];
    t[y] = x;
  }
  else if(h[x] > h[y]) {
    t[y] = x;
  }
  else {
    t[x] = y;
  }
}

int main()
{
  int n, m, i, x, y, sol1 = 0, k = 0;
  freopen("apm.in","r",stdin);
  freopen("apm.out","w",stdout);
  scanf("%d%d", &n, &m);
  for(i = 1;i <= n; ++i) {
    t[i] = i;
    h[i] = 1;
  }
  for(i = 1;i <= m; ++i) {
    scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
  }
  sort(v + 1, v + m + 1, cmp);
  for(i = 1;i <= m; ++i) {
    x = FindSet(v[i].x);
    y = FindSet(v[i].y);
    if(x != y) {
      UnionSet(x, y);
      sol1 += v[i].cost;
      sol[++k].x = v[i].x;
      sol[k].y = v[i].y;
    }
  }
  printf("%d\n%d\n", sol1, k);
  for(i = 1;i <= k; ++i) {
    printf("%d %d\n", sol[i].x, sol[i].y);
  }
  return 0;
}