#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");

const int N = 200001, M = 400004;
bool folosit[M];
int nr[M];
int t[N];
struct muchie {
    int x,y,c;
} v[M];

int radacina ( int x )
{
    if ( t[x] == 0 )
    {
        return x;
    }
    t[x] = radacina(t[x]);
    return t[x];
}

bool comp ( muchie a, muchie b)
{
    return a.c < b.c;
}

bool verif ( int x, int y )
{
    return ( radacina(x) == radacina(y) );
}

void reuniune (int x, int y)
{
    int rx = radacina (x);
    int ry = radacina (y);
    if ( rx == ry)
    {
        return;
    }
    if ( nr[rx] < nr[ry] )
    {
        nr[ry]+= nr[rx];
        t[rx] = ry;
    }
    else
    {
        nr[rx]+= nr[ry];
        t[ry] = rx;
    }
}

int main ()
{
    int n, m, cost = 0, cate = 0;
    in >> n >> m;
    for ( int i = 0; i < m; i++ )
    {
        int x, y, c;
        in >> x >> y >> c;
        v[i].x = x;
        v[i].y = y;
        v[i].c = c;
    }
    sort( v, v+m, comp);
    for ( int i = 0; i < m; i++ )
    {
        if (!verif(v[i].x, v[i].y))
        {
            folosit[i] = true;
            cate++;
            cost += v[i].c;
            reuniune ( v[i].x, v[i].y);
        }
    }
    out << cost << "\n" << cate << "\n";
    for ( int i = 0; i < m; i++ )
    {
        if ( folosit[i] )
        {
           out << v[i].x << " " << v[i].y <<"\n";
        }
    }
    return 0;
}