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