#include <bits/stdc++.h>

using namespace std;

struct nod {
    int u, v, c;
};

struct muchie {
    int u, v;
};

#define MAXN 200000
vector<nod> g;
vector<muchie> ans;
int sef[MAXN + 1];

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

bool cmp( nod a, nod b ) {
    return a.c < b.c;
}

int findSef( int i ) {
    if( sef[i] == i )
        return i;
    return sef[i] = findSef( sef[i] );
}

void unionSef( int i, int j ) {
    int sefi, sefj;

    sefi = findSef( i );
    sefj = findSef( j );

    sef[sefj] = sefi;
}

int main() {
    int n, m, i, u, v, c, sum, cnt;

    fin >> n >> m;
    for( i = 1; i <= m; i++ ) {
        fin >> u >> v >> c;
        g.push_back( { u, v, c } );
    }
    sort( g.begin(), g.end(), cmp );

    for( i = 1; i <= n; i++ )
        sef[i] = i;
    sum = 0;
    i = 0;
    while( cnt < n - 1 ) {
        if( findSef( g[i].u ) != findSef( g[i].v ) ) {
            sum += g[i].c;
            cnt++;
            ans.push_back( { g[i].u, g[i].v } );
            unionSef( g[i].u, g[i].v );
        }
        i++;
    }

    fout << sum << '\n' << ans.size() << '\n';
    for( i = 0; i < ans.size(); i++ )
        fout << ans[i].v << ' ' << ans[i].u << '\n';
    return 0;
}