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

using namespace std;

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

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

const int NMAX = 200000 + 1;
int n, m, cost;
vector <Muchie> muchii;
int t[NMAX], h[NMAX];

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++) {
        t[i] = i;
        h[i] = 1;
    }
}

void uneste(int x, int y) {
    if (h[x] < h[y]) t[x] = y;
    else t[y] = x;
    if (h[x] == h[y]) h[x]++;
}

int radacina(int x) {
    while (t[x] != x) x = t[x];
    return x;
}

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

void APM() {
    int rx, ry;
    for (int i = 0; i < m; i++) {
        rx = radacina(muchii[i].a);
        ry = radacina(muchii[i].b);
        if (rx != ry) {
            uneste(rx, ry);
            muchii[i].pus = true;
            cost += muchii[i].cost;
        }
    }
}

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

int main() {
    citeste();
    initializeaza();
    sort(muchii.begin(), muchii.end(), conditie);
    APM();
    scrie();
    return 0;
}