#include <iostream>
#include <algorithm>
#include <fstream>
#define MMAX 400000
#define NMAX 200000
using namespace std;

struct str {
    int x, y, cost, g;
} muchii[MMAX];

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

int sef[NMAX+1];
bool cmp( str a, str b ) {
    return a.cost < b.cost;
}

int find_sef( int node ) {
    if( node == sef[node] )
        return node;
    return sef[node] = find_sef( sef[node] );
}

int main() {
    int n, m;
    fin >> n >> m;
    for( int i = 0; i < m; i++ ) {
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
        muchii[i].g = 0;
    }
    sort( muchii, muchii + m, cmp );
    
    for( int i = 1; i <= n; i++ ) sef[i] = i;
    int total = 0;
    
    for( int i = 0; i < m; i++ ) {
        int x = muchii[i].x, y = muchii[i].y;
        if( find_sef( x ) != find_sef( y ) ) {
            sef[find_sef( x )] = find_sef( y );
            total += muchii[i].cost;
            muchii[i].g = 1;
        }
    }
    
    fout << total << '\n' << n - 1 << '\n';
    for( int i = 0; i < m; i++ )
        if( muchii[i].g )
            fout << muchii[i].x << ' ' << muchii[i].y << '\n';
    
    return 0;
}