#include <iostream>
#include <fstream>
#include <algorithm>


using namespace std;

#define nmax 200002

struct info {
    int cost, a, b;
};

info edges[nmax*2];


bool sortare(const info& a, const info& b ) {
    if( a.cost < b.cost )
        return 1;
    return 0;
}

int parinte[nmax], rasp[nmax];


int sef( int x ) {
    int aux;
    if( parinte[x] == x )
        return x;
    aux = sef( parinte[x] );
    parinte[x] = aux;
    return aux;

}


int main()
{
    int n, m, i, x, y, k = 0, aa, bb;
    long long c = 0;
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;

    for( i = 1; i <= n; i++ )
        parinte[i] = i;

    for( i = 0; i < m; i++ )
        cin >> edges[i].a >> edges[i].b >> edges[i].cost;

    sort( edges, edges+m, sortare );

    for( i = 0; i < m; i++ ) {
        x = edges[i].a;
        y = edges[i].b;
        if( sef(x) != sef(y) ) {
            aa = sef(x);
            bb = sef(y);
            parinte[aa] = bb;
            c = c + edges[i].cost;
            rasp[k] = i;
            k++;
        }
    }

    cout << c << "\n" << n-1 << "\n";
    for( i = 0; i < k; i++ )
        cout << edges[rasp[i]].a << " " << edges[rasp[i]].b << "\n";

    return 0;
}