#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

#define Nmax 200002

ifstream fin( "apm.in" );
ofstream fout( "apm.out" );

vector < pair < int, int > > G[Nmax], Edges;
priority_queue < pair < int, pair < int, int > > > Heap;
bitset < Nmax > inAPM;

int APM_Prim(){

    int Total = 0;

    Heap.push( make_pair( 0, make_pair( 1, 0 ) ) );

    while( !Heap.empty() ){
        int val = -Heap.top().first;
        int nod = Heap.top().second.first;
        int pred = Heap.top().second.second;
        Heap.pop();

        if( inAPM[nod] )
            continue;

        inAPM[nod] = 1;
        Total += val;

        if( pred )
            Edges.push_back( make_pair( nod, pred ) );

        vector < pair < int, int > > :: iterator it;
        for( it = G[nod].begin(); it != G[nod].end(); ++it )
            if( !inAPM[it->first] )
                Heap.push( make_pair( -it->second, make_pair( it->first, nod ) ) );
    }

    return Total;
}


int main(){

    int N, M;

    fin >> N >> M;

    int x, y, c;
    while( M-- ){
        fin >> x >> y >> c;
        G[x].push_back( make_pair( y, c ) );
        G[y].push_back( make_pair( x, c ) );
    }

    vector < pair < int, int > > :: iterator it;

    fout << APM_Prim() << "\n" << N-1 << "\n";
    for( it = Edges.begin(); it != Edges.end(); ++it )
        fout << it -> first << " " << it -> second << "\n";

    return 0;
}