#include <iostream>
#include <fstream>
#define Nmax 200005
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int n , m , cst, p[Nmax];
vector < pair < int, int > > rsp;

struct much
{
    int x, y, cost;
}muchie[Nmax];

bool cmp ( much A , much B)
{
    return A . cost < B. cost;
}
int parinte(int nod)
{
    if ( p [ nod ] == nod) return nod;
    return p [ nod ] = parinte ( p [ nod ] );
}
void un ( int nod1 , int nod2)
{
    p [ parinte ( nod2 ) ] = parinte ( nod1 );
}
int main()
{
    fin >> n >> m ;
    for ( int i = 1; i <= m ; i++ )
        fin >> muchie [ i ] . x >> muchie [ i ] . y >> muchie [ i ] . cost;

    for ( int i = 1; i <= n; i ++ ) p[i] = i;
    sort ( muchie + 1 , muchie + m + 1 , cmp ) ;

    for ( int i = 1; i <= m; i++ )
    {
        if ( parinte ( muchie [ i ] . x ) != parinte ( muchie [ i ] . y ) )
        {
            un ( parinte ( muchie [ i ] . x ) , parinte ( muchie [ i ] . y) );
            cst += muchie [ i ] . cost;
            rsp . push_back ( { muchie [ i ] . x , muchie [ i ] . y } );
        }
    }

    fout << cst << '\n';
    fout << rsp.size() << '\n';
    for ( int i = 0 ; i < rsp.size(); i++ )
        fout << rsp [ i ] . first << " " << rsp [ i ] . second << '\n';

    return 0;
}