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

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

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

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

int Root(int x)
{
    while(T[x] != x)
        x = T[x];
    return x;
}

void Unifica(int x, int y)
{
    if(P[x] < P[y])
        T[x] = y;
    if(P[x] > P[y])
        T[y] = x;
    if(P[x] == P[y]){
        T[y] = x;
        P[x]++;
    }
}

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);
        T[i] = i; /// 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 = Root(u[i].x);
        int ry = Root(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;
}