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

#define nmax 200001

using namespace std;


struct edge{
    int u, v, c;
    bool operator < ( const edge &x ) const {
        return c < x.c;
    }
};

edge edges[nmax];
int parinte[nmax], arbore[nmax][2];

int find_daddy( int a ) {
    int x;
    if( a == parinte[a] )
        return a;
    x = find_daddy( parinte[a] );
    parinte[a] = x;
    return x;
}

void uniune( int a, int b ) {
    int x, y;
    x = find_daddy( a );
    y = find_daddy( b );
    parinte[x] = y;
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m, i, x, y, cost, s = 0, muchii = 0;
    cin >> n >> m;
    for( i = 0; i < m; i++ ) {
        cin >> x >> y >> cost;
        edges[i].u = x;
        edges[i].v = y;
        edges[i].c = cost;
    }

    sort( edges, edges+m );

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

    for( i = 0; i < m; i++ ) {
        x = find_daddy( edges[i].u );
        y = find_daddy( edges[i].v );
        if( x != y ) {
            parinte[x] = y;
            s += edges[i].c;
            arbore[muchii][0] = edges[i].u;
            arbore[muchii][1] = edges[i].v;
            muchii++;
        }
    }

    cout << s << "\n" << n - 1 << "\n";
    for( i = 0; i < muchii; i++ )
        cout << arbore[i][0] << " " << arbore[i][1] << "\n";

    return 0;
}