// Arborele partial de cost minim
// Algoritmul lui Kruskal

# include <fstream>
# include <algorithm>
# include <vector>
# define fi first.first
# define sec first.second
# define cost second

using namespace std;

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

int n, m, total;
vector < pair < pair < int, int >, int > > v; // retinem muchiile
vector < pair < int, int > > answer; // vector pentru muchiile folosite in arbore
vector < int > c; // componente

int compare( pair < pair < int, int >, int > P1, pair < pair < int, int >, int > P2 ) { // compare pentru sort
    if ( P1.second < P2.second )
        return 1;
    return 0;
}

int componenta( int x ) {
    while ( c[x] != x )
        x = c[x];
    return x;
}

void Read() { // functie citire

    f >> n >> m;
    for ( int i = 0; i < m; ++ i ) {
        int x, y, c;
        f >> x >> y >> c;
        v.push_back( make_pair( make_pair( x, y ), c ) );
    }
}

void Kruskal() { // Algoritmul lui Kruskal

    sort( v.begin(), v.end(), compare ); // sortare dupa cost

    c.resize( n + 1 );
    for ( int i = 1; i <= n; ++ i ) { // initial toate muchiile fac parte din componente diferite
        c[i] = i;
    }

    int edges = 0; // numarul de muchii adaugate in arbore; initial este 0
    for ( int i = 0; i < m && edges < n - 1; ++ i ) {
        int a = componenta( v[i].fi );
        int b = componenta( v[i].sec );
        if ( a != b ) { // daca componenta lui x este diferita de componenta lui y, adaugam xy in arbore
            ++ edges;
            total = total + v[i].cost; // adaugam costul muchiei la costul total
            answer.push_back( make_pair( v[i].fi, v[i].sec ) ); // muchia face parte din arbore
            if ( a > b ) c[b] = a; // update componente
            else c[a] = b;
        }
    }
}

void Afisare() { // functie afisare

    g << total << '\n';
    g << n - 1 << '\n';
    for ( auto it: answer ) {
        g << it.first << " " << it.second << '\n';
    }
}

void Solve() { // Rezolvare

    Read();
    Kruskal();
    Afisare();
}

int main()
{
    Solve();

    return 0;
}