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

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

const int nmax = 200000;

int n, m;
int cost, nrmuchii;
struct Muchie {
    int a, b, cost;
    bool kept;
    Muchie (int a, int b, int cost) {
        this->a = a;
        this->b = b;
        this->cost = cost;
        this-> kept = false;
    };
};

int v[nmax + 1];
vector <Muchie> muchii;

void citeste () {
    f >> n >> m;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        muchii.push_back (Muchie (a, b, c));
    }
}

bool conditie (Muchie a, Muchie b) {
    return a.cost < b.cost;
}


void update (int x, int y) {
    if (x > y) swap (x, y);
    for (int i = 1; i <= n; i++)
        if (v[i] == y) v[i] = x;
}

void APM () {
    for (int i = 0; i < m; i++) {
        if (v[muchii[i].a] != v[muchii[i].b]) {
            nrmuchii++;
            cost += muchii[i].cost;
            muchii[i].kept = true;
            update (v[muchii[i].a], v[muchii[i].b]);
            //for (int i = 1; i <= n; i++) cout << v[i] << ' ';
            //cout << endl;
        }
    }
}

void scrie () {
    g << cost << '\n' << nrmuchii << '\n';
    for (int i = 0; i < m; i++)
        if (muchii[i].kept) g << muchii[i].a << ' ' << muchii[i].b << '\n';
}

int main () {
    citeste ();

    for (int i = 1; i <= n; i++) v[i] = i;
    sort (muchii.begin (), muchii.end (), conditie);

    APM ();

    scrie ();

    return 0;
}