#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5;

int father[NMAX + 1];
int siz[NMAX + 1];

int root( int a ) {
    if ( father[a] == a ) {
        return a;
    }
    return ( father[a] = root( father[a] ) );
}
bool unite( int a, int b ) {
    a = root( a );
    b = root( b );
    if ( a == b ) return false;
    if ( siz[a] < siz[b] ) {
        swap( a, b );
    }
    father[b] = a;
    siz[a] += siz[b];
    return true;
}
int main() {
    ifstream fin( "apm.in" );
    ofstream fout( "apm.out" );
    int n, m;
    fin >> n >> m;
    for ( int i = 1; i <= n; i ++ ) {
        father[i] = i;
        siz[i] = 1;
    }
    vector <pair <int, pair<int, int>>> edges;

    for ( int i = 1, a, b, c; i <= m; i ++ ) {
        fin >> a >> b >> c;
        edges.push_back( {c, {a, b} } );
    }
    sort( edges.begin(), edges.end() );
    vector <pair<int, int>> muchii;

    long long totalCost = 0;
    for ( auto p : edges ) {
        int c = p.first, a = p.second.first, b = p.second.second;
        if ( unite( a, b ) ) {
            totalCost += c;
            muchii.push_back( {a, b} );
        }
    }
    fout << totalCost << '\n';
    fout << muchii.size() << '\n';
    for ( auto p : muchii ) {
        fout << p.first << ' ' << p.second << '\n';
    }
    return 0;
}