#include <iostream>
#include <cstdio>
#include <algorithm>
#define NMAX 200005
#define MMAX 400005

using namespace std;

int n, m, p[NMAX], totalSum, nrSol;
struct vertice{
   int a, b, c;
};
vertice v[MMAX], sol[NMAX];

bool cmp(vertice A, vertice B)
{
   return A.c < B.c;
}

void read()
{
   scanf("%d %d\n", &n, &m);
   for (int i=0; i<m; i++){
      scanf("%d %d %d\n", &v[i].a, &v[i].b, &v[i].c);
   }
   sort(v, v+m, cmp);
}

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

void unify(int x, int y)
{
   p[getGroup(x)] = getGroup(y);
}

void kruskal()
{
   for (int i=1; i<=n; i++)
      p[i] = i;

   for (int i=0; i<m; i++){
      if (getGroup(v[i].a) != getGroup(v[i].b)){
         unify(v[i].a, v[i].b);
         totalSum += v[i].c;
         sol[++nrSol] = v[i];
      }
   }

   printf("%d\n%d\n", totalSum, nrSol);
   for (int i=1; i<=nrSol; i++){
      printf("%d %d\n", sol[i].a, sol[i].b);
   }
}

int main()
{
   freopen("apm.in", "r", stdin);
   freopen("apm.out", "w", stdout);
   read();
   kruskal();

   return 0;
}