#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int x, y, c;
};

#define pb push_back
#define VI vector<int>
#define VM vector<muchie>

int n, m;
VI tata, rang;
VM muchiiGraf, sol;

bool cmp(muchie u1, muchie u2) {
    return u1.c < u2.c;
}

int repr(int nod) {
    if (tata[nod] == 0) {
        return nod;
    }
    int x = repr(tata[nod]);
    tata[nod] = x;
    return x;
}

void unire(int subArbX, int subArbY) {
    if (rang[subArbX] < rang[subArbY]) {
        tata[subArbX] = subArbY;
    } else {
        tata[subArbY] = subArbX;
        if (rang[subArbX] == rang[subArbY]) {
            ++rang[subArbX];
        }
    }
}

void Kruskal(int &cost) {
    for (auto u : muchiiGraf) {
        int subArbX = repr(u.x),
            subArbY = repr(u.y);
        if (subArbX != subArbY) {
            cost += u.c;
            sol.pb(u);
            unire(subArbX, subArbY);
        }
    }
}

int main() {
    fin >> n >> m;
    tata = rang = VI(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        muchie u;
        fin >> u.x >> u.y >> u.c;  
        muchiiGraf.pb(u);
    }

    sort(muchiiGraf.begin(), muchiiGraf.end(), cmp);

    int cost = 0;

    Kruskal(cost);

    fout << cost << '\n' << sol.size() << '\n';
    for (auto u : sol) {
        fout << u.x << ' ' << u.y << '\n';
    }
}
/*
Idee algoritm kruskal:
Ordonam muchiile crescator dupa costul lor;
Pentru obtinerea APM vom lua pe rand muchiile si vom verifica daca
muchia curenta uneste doi subarbori diferiti.
Daca conditia este adevarata, facem reuniunea arborilor
Altfel muchia va fi ignorata
*/