#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 2e5;
const int MMAX = 4e5;

struct edge{
    int a;
    int cost;
};

vector <edge> edges[MMAX];
vector <edge> arbore[NMAX];
int viz[NMAX];

struct node {
    int a;
    int cost;
    int anc;
} heap[MMAX];
int h;

void update( int node, int cost, int anc ) {
    int i = h;
    heap[h++] = { node, cost, anc };
    while ( i > 0 && heap[( i - 1 ) / 2].cost > heap[i].cost ) {
        swap( heap[i], heap[( i - 1 ) / 2] );
        i /= 2;
    }
}
void pop() {
    int i = 0;
    swap( heap[0], heap[--h] );
    while ( i * 2 + 2 < h && heap[i].cost > min( heap[i * 2 + 1].cost, heap[i * 2 + 2].cost ) ) {
        if ( heap[i * 2 + 1].cost < heap[i * 2 + 2].cost ) {
            swap( heap[i], heap[i * 2 + 1] );
            i = i * 2 + 1;
        } else {
            swap( heap[i], heap[i * 2 + 2] );
            i = i * 2 + 2;
        }
    }
    if ( i * 2 + 1 < h && heap[i].cost > heap[i * 2 + 1].cost )
        swap( heap[i], heap[i * 2 + 1] );
}

int apm() {
    int node, cost, total = 0;
    update( 0, 0, 0 );
    while ( h > 0 ) {
        if ( viz[heap[0].a] ) {
            pop();
        } else {
            node = heap[0].a;
            cost = heap[0].cost;
            arbore[node].push_back( { heap[0].anc, cost } );
            total += heap[0].cost;
            pop();
            viz[node] = 1;
            for ( auto& x : edges[node] ) {
                if ( !viz[x.a] ) {
                    update( x.a, x.cost, node );
                }
            }
        }
    }
    swap( arbore[0][0], arbore[0][arbore[0].size() - 1] );
    arbore[0].pop_back();
    return total;
}
int main() {
    ifstream fin( "apm.in" );
    ofstream fout( "apm.out" );
    int n, m, i, a, b, cost;
    fin >> n >> m;
    for ( i = 0; i < m; i ++ ) {
        fin >> a >> b >> cost;
        a --;
        b --;
        edges[a].push_back( { b, cost } );
        edges[b].push_back( { a, cost } );
    }
    fout << apm() << '\n' << n - 1 << '\n';
    for ( i = 0; i < n; i ++ ) {
        for ( auto& x : arbore[i] )
            fout << i + 1 << ' ' << x.a + 1 << '\n';
    }
    return 0;
}