# include <cstdio>
# include <algorithm>
using namespace std;

struct muchie {
    int x, y, c;
}u[200005], sol[200005];

int n, m, k, i, ct, P[200005], j, nr1, nr2;

bool cmp(muchie x, muchie y )
{
    return x.c < y.c;
}

int Radacina(int i)
{
    int k;
    k = i;
    while (P[k] > 0)
        k = P[k];
    while (P[i] > 0) {
        P[i] = k;
        i = P[i];
    }
    return i;
}

void Unifica(int i, int j)
{
    P[i] += P[j];
    P[j] = i;
}

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

   scanf("%d %d", &n, &m);
   for (i=1; i<=m; ++i) {
        scanf("%d %d %d", &u[i].x, &u[i].y, &u[i].c);
        P[i] = -1; /// padurea de arbori indepedenti
    }

   ///sortam crescator dupa cost
   sort(u+1, u+m+1, cmp);

   i = 1;
   while (k < n-1) {
       ///muchia (x,y)
        int rx = Radacina(u[i].x);
        int ry = Radacina(u[i].y);
        if (rx != ry){
             ++k;
             ct += u[i].c;
             sol[k] = u[i];
             Unifica(rx, ry);
        }
         ++i;
    }

  printf("%d\n%d\n", ct, k);
  for (i=1; i<=k; ++i)
      printf("%d %d\n", sol[i].x, sol[i].y);

  return 0;
}