#include <bits/stdc++.h>
#define DIM 400005
#define cost first
#define st second.first
#define dr second.second

using namespace std;

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

int n, m, c, x, y, rx, ry, s, k, cont;
pair< int,  pair<int, int> > l[DIM];
int viz[DIM], t[DIM], p[DIM], u[DIM];

int rad( int x )
{
    while( t[x] > 0 )
        x= t[x];
    return x;
}

int main()
{

    for(int i = 1; i <= DIM; i++)
        t[i] = -1;

    in>>n>>m;

    for(int i = 1; i <= m; i++){

        in>>x>>y>>c;

        l[i].cost = c;
        l[i].st = x;
        l[i].dr = y;
    }

    sort( l + 1, l + m + 1 );

    for(int i = 1; i <= m; i++){

        rx = rad( l[i].st );
        ry = rad( l[i].dr );

        if( rx != ry ){
            s += l[i].cost;
            p[++k] = l[i].st;
            u[k] = l[i].dr;

            if( t[rx] < t[ry] ){
                t[rx] += t[ry];
                t[ry] = rx;
            } else {
                t[ry] += t[rx];
                t[rx] = ry;
            }
        }
    }

    out<<s<<"\n";
    for( int i = 1; i <= n; i++ )
        if( t[i] != -1 )
            cont++;
    out<<cont - 1<<"\n";

    for( int i = 1; i <= k; i++ )
        out<<p[i]<<" "<<u[i]<<"\n";

    return 0;
}