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

using namespace std;

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

const int NMAX = 200000 + 1, MMAX = 400000 + 1;

struct Muchie {
    int a, b, cost;
    bool selectat;
    Muchie(int a, int b, int cost) {
        this->a = a;
        this->b = b;
        this->cost = cost;
        this->selectat = false;
    };
};

int n, m;
vector <Muchie> muchii;
int tata[NMAX], rang[NMAX];

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

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

void initializeaza() {
    for (int i = 1; i <= n; i++) {
        tata[i] = i;
        rang[i] = 1;
    }
}

int radacina(int x) {
    if (tata[x] == x) return x;
    tata[x] = radacina(tata[x]);
    return tata[x];
}

void uneste(int a, int b) {
    a = radacina(a);
    b = radacina(b);
    if (rang[b] > rang[a]) tata[a] = b;
    else tata[b] = a;
    if (rang[a] == rang[b]) rang[a]++;
}

bool sunt_unite(int a, int b) {
    a = radacina(a);
    b = radacina(b);
    return a == b;
}

void apm() {
    int a, b, cost_total, nr_muchii;
    sort(muchii.begin(), muchii.end(), comp);
    initializeaza();
    cost_total = nr_muchii = 0;

    for (int i = 0; i < m; i++) {
        a = muchii[i].a;
        b = muchii[i].b;
        if (sunt_unite(a, b)) continue;
        uneste(a, b);
        muchii[i].selectat = true;
        nr_muchii++;
        cost_total += muchii[i].cost;
    }

    g << cost_total << '\n' << nr_muchii << '\n';
    for (int i = 0; i < m; i++)
        if (muchii[i].selectat) g << muchii[i].a << ' ' << muchii[i].b << '\n';
}

int main() {
    citeste();
    apm();
    return 0;
}