#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define fst first.first
#define sec first.second
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m, costtotal;
vector < pair < pair < int, int >, int > > v;
vector < pair < int, int > > apm;
vector < int > compon;
int componenta( int x )
{
    while ( compon[x] != x )
        x = compon[x];
    return x;
}
int compara( pair < pair < int, int >, int > a, pair < pair < int, int >, int > b )
{

    if ( a.second < b.second )
        return 1;
    return 0;
}
void Kruskal()
{
    int c1,c2,add;

    compon.resize( n + 1 );
    for ( int i = 1; i <= n; ++ i )
        compon[i] = i;
    sort( v.begin(), v.end(), compara );
    add = 0;
    for ( int i = 0; i < m && add < n - 1; ++ i )
    {
        c1 = componenta( v[i].fst );
        c2 = componenta( v[i].sec );
        if ( c1!= c2)
        {
            add+=1;
            costtotal = costtotal + v[i].second;
            apm.push_back( make_pair( v[i].fst, v[i].sec ) );
            if ( c1 > c2 ) compon[c1] = c2;
            else compon[c1] = c2;
        }
    }
}

int main()
{
    int x, y, cost;
    f >> n >> m;
    for ( int i = 0; i < m; ++ i )
    {
        f >> x >> y >> cost;
        v.push_back( make_pair( make_pair( x, y ), cost ) );
    }
    Kruskal();
    g << costtotal <<'\n';
    g << n - 1 << '\n';
        for ( auto it: apm )
        g << it.first << " " << it.second << '\n';


    return 0;
}