#include <fstream>
#include <algorithm>
#define nmax 200005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int tt[nmax];
int n, m, c, x, y, N, X, Y, sm, x1, y1, i ;

struct edge{
int x, y, c;
}e[nmax], sol[2*nmax];

bool cmp(edge a, edge b)
{
    return a.c < b.c;
}

int upd(int x)
{
    int r = x, y;
    while( tt[r] != r ) r = tt[r];
    while( tt[x] != x )
     {
        y = tt[x];
        tt[x] = r;
        x = y;
     }
    return r;
}

int main()
{
    f >> n >> m;
     for (  i = 1 ; i <= n ; i ++ )
       tt[i] = i;
    for (  i = 1 ; i <= m ; i ++ )
         f >> e[i].x >> e[i].y >> e[i].c;
     sort( e+1, e+m+1, cmp );

     for (  i = 1 ; i <= m ; i ++ )
     {
          x1 = e[i].x, y1 = e[i].y;
          X = upd(x1), Y = upd(y1);
          if (X != Y)
           {
            sm += e[i].c;
            tt[X] = Y;
            sol[++N] = {x1,y1,100};
           }
     }
      g << sm << '\n' << N << '\n';
    for ( i = 1; i <= N; i++)
        g << sol[i].x << ' ' << sol[i].y << '\n';

    return 0;
}