#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

#define magic_sauce inline __attribute__((always_inline))

using namespace std;

const int NMAX = 2e5;

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

vector <pair<int, int>> edges[NMAX + 1];
bool viz[NMAX + 1];

void prim( int n ) {
    long long ans = 0;
    vector <pair<int, int>> e;

    priority_queue <pair<pair<int, int>, int>> pq;
    pq.push( { {0, -1}, 1 } );
    while ( !pq.empty() ) {
        auto p = pq.top();
        pq.pop();
        if ( viz[p.second] ) continue;
        viz[p.second] = true;

        ans += -p.first.first;
        e.push_back( { p.first.second, p.second } );
        for ( auto e : edges[p.second] ) {
            if ( !viz[e.first] ) {
                pq.push( { { -e.second, p.second }, e.first } );
            }
        }
    }
    fout << ans << '\n' << n - 1 << '\n';
    for ( auto p : e ) {
        if ( p.first != -1 ) fout << p.first << ' ' << p.second << '\n';
    }
//    for ( int i = 1; i <= n; i ++ ) {
//        if ( !viz[i] ) return INF;
//    }
//    return ans;
}
int main() {
//    ios_base::sync_with_stdio( false );
//    cin.tie( NULL );
//    cout.tie( NULL );
    int n, m;
    fin >> n >> m;
    for ( int i = 1, a, b, c; i <= m; i ++ ) {
        fin >> a >> b >> c;
        edges[a].push_back( { b, c } );
        edges[b].push_back( { a, c } );
    }
    prim( n );
    return 0;
}