#include <bits/stdc++.h>

using namespace std;

struct muchie{
    int st, fn, cost;
};

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

bool cmp( muchie a, muchie b ) {
    return a.cost < b.cost;
}

int daddy[400005];

muchie cop[400005];

int get_big_daddy( int a ) {
    if ( a == daddy[a] ) {
        return a;
    }
    return daddy[a] = get_big_daddy( daddy[a] );
}

int join ( int a, int b ) {
    a = get_big_daddy( a );
    b = get_big_daddy( b );
    if ( a != b ) {
        daddy[b] = a;
    }
}

muchie v[400005];

int main() {
    int n, m;
    fin >> n >> m;
    for ( int i = 1; i <= m; i++ ) {
        int x, y, cs;
        fin >> x >> y >> cs;
        v[i].st = x;
        v[i].fn = y;
        v[i].cost = cs;
    }

    sort( v + 1, v + m + 1, cmp );

    for ( int i = 1; i <= n; i++ ) {
        daddy[i] = i;
    }

    int sum = 0;
    int j = 1;
    for ( int i = 1; i <= m; i++ ) {
        if ( get_big_daddy( v[i].st ) != get_big_daddy( v[i].fn ) ) {
            sum += v[i].cost;
            cop[j].st = v[i].st;
            cop[j].fn = v[i].fn;
            join( v[i].st, v[i].fn );
            j++;
        }
    }
    fout << sum << '\n' << n - 1 << '\n';
    for ( int i = 1; i < j; i++ ) {
        fout << cop[i].st << ' ' << cop[i].fn << '\n';
    }

    return 0;
}