#include <fstream>
#include <algorithm>

#define st second.first
#define dr second.second
#define cost first
#define din 200000
#define dim 400000

using namespace std;

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

pair < int, pair <int, int> >  l[din];

int n, i, x, y, z, m, t[dim], p[dim], u[dim], rx, ry, s, k;

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

int main()
{
    f >> n >> m;
    for( i = 1; i <= m; i ++)
        f >> l[i].st >> l[i].dr >> l[i].cost;

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

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

    for(i = 1; i <= m; i ++)
    {
        rx = rad(l[i].st);
        ry = rad(l[i].dr);

        if( ry != rx )
        {
            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;
            }
        }
    }

    g << s << '\n' << k << '\n';

    for( i = 1; i <= k; i ++ )
        g << p[i] << ' ' << u[i] << '\n';

    return 0;
}