#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie {
    int x, y, cost;
    bool operator<(const Muchie &m) const {
        return cost < m.cost;
    }
};
int gaseste(int nod, vector<int> &parinte) {
    if (parinte[nod] != nod) parinte[nod] = gaseste(parinte[nod], parinte);
    return parinte[nod];
}
void uneste(int a, int b, vector<int> &parinte, vector<int> &rang) {
    int radA = gaseste(a, parinte);
    int radB = gaseste(b, parinte);
    if (radA != radB) {
        if (rang[radA] > rang[radB]) {
            parinte[radB] = radA;
        } else if (rang[radA] < rang[radB]) {
            parinte[radA] = radB;
        } else {
            parinte[radB] = radA;
            rang[radA]++;
        }
    }
}
int main() {
    int n, m;
    fin >> n >> m;
    vector<Muchie> muchii(m);
    for (int i = 0; i < m; i++) fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
    sort(muchii.begin(), muchii.end());
    vector<int> parinte(n + 1), rang(n + 1, 0);
    for (int i = 1; i <= n; i++) parinte[i] = i;
    vector<Muchie> arbore;
    int cost_total = 0;
    for (int i = 0; i < m; i++) {
        int nod1 = muchii[i].x;
        int nod2 = muchii[i].y;
        int cost = muchii[i].cost;
        if (gaseste(nod1, parinte) != gaseste(nod2, parinte)) {
            uneste(nod1, nod2, parinte, rang);
            arbore.push_back(muchii[i]);
            cost_total += cost;
        }
        if ((int)arbore.size() == n - 1) break;
    }
    fout << cost_total << "\n";
    fout << arbore.size() << "\n";
    for (int i = 0; i < (int)arbore.size(); i++) fout << arbore[i].y << " " << arbore[i].x << "\n";
    return 0;
}