#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;

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 ( int i = 1 ; i <= n ; i ++ )
       tt[i]=i;
    for ( int i = 1 ; i <= m ; i ++ )
         f >> e[i].x >> e[i].y >> e[i].c;
     sort(e+1, e+m+1, cmp);

     for ( int 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 (int i = 1; i <= N; i++)
        g << sol[i].x << ' ' << sol[i].y << '\n';

    return 0;
}