// 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 compare( pair < pair < int, int >, int > P1, pair < pair < int, int >, int > P2 ) { // compare pentru sort
    if ( P1.cost < P2.cost )
        return 1;
    return 0;
}

class Graf { // Clasa Graf

    int n, m, total = 0;
    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 componenta( int x );

public:
    Graf();
    ~Graf();
    void Read();
    void Kruskal();
    void Afisare();
    void Solve();
};

Graf :: Graf(){
    // Nu face nimic
}

Graf :: ~Graf() {
    // ...
}

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

void Graf :: 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 Graf :: Kruskal() { // Algoritmul lui Kruskal

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

    c.resize( n + 1 ); // vectorul pentru cele n varfuri
    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 ) { // cat timp arborele nu e complet
        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 Graf :: Afisare() { // functie afisare

    g << total << '\n'; // costul total
    g << n - 1 << '\n'; // numarul de muchii
    for ( auto it: answer ) {
        g << it.first << " " << it.second << '\n'; // muchiile arborelui
    }
}

void Graf :: Solve() { // Rezolvare

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

// Clasa Graf - End

int main()
{
    Graf G;
    G.Solve();

    return 0;
}