#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct ura{
    int x, y, cost;
};
ura muchii[400005], sol[200005];
int sef[200005], n, m, k;
long long cost_tot;
bool cmp( ura a, ura b ){
    if( a.cost < b.cost )
        return true;
    return false;
}
int gasire( int x ){
    if( sef[x] == x )
        return x;
    return sef[x]=gasire(sef[x]);
}
void unire( int x, int y ){
    x=gasire(x);
    y=gasire(y);
    if( x != y )
        sef[x]=y;
}
int main(){
    int i;
    cin>>n>>m;
    for( i = 1; i <= m; i++ )
        cin>>muchii[i].x>>muchii[i].y>> muchii[i].cost;
    sort( muchii + 1, muchii + m + 1, cmp );
    for( i = 1; i <= n; i++ )
        sef[i]=i;
    for( i = 1; i <= m && k < n - 1; i++ )
        if( gasire(muchii[i].x) != gasire(muchii[i].y) ) {
            unire(muchii[i].x,muchii[i].y);
            sol[++k]=muchii[i];
            cost_tot+=muchii[i].cost;
        }
    cout<<cost_tot<<'\n'<<k<<'\n';
    for( i = 1; i <= k; i++ )
        cout<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}