#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

// Structura unei muchii
struct Muchie {
    int x, y, cost;
};

// Vectorii DSU
vector<int> parinte;
vector<int> sz;

// Inițializează structura DSU
void initializeaza_DSU(int n) {
    parinte.resize(n + 1);
    sz.resize(n + 1);

    for (int i = 1; i <= n; i++) {
        parinte[i] = i;
        sz[i] = 1;       // fiecare mulțime are mărimea 1 la început
    }
}

// Găsește reprezentantul unei mulțimi (path compression)
int gaseste(int x) {
    if (x == parinte[x])
        return x;
    return parinte[x] = gaseste(parinte[x]);
}

// Unifică cele două mulțimi folosind "size" (mărimea mulțimii)
void unire(int a, int b) {
    // atașăm arborele mai mic la cel mai mare
    if (sz[a] < sz[b])
        swap(a, b);

    parinte[b] = a;
    sz[a] += sz[b];
}

// Verifică dacă adăugarea unei muchii formează un arbore
bool arbore(int u, int v) {
    int a = gaseste(u);
    int b = gaseste(v);

    if (a == b)
        return false;   // formează ciclu → nu este arbore

    // putem adăuga muchia → facem unirea AICI
    unire(a, b);
    return true;
}

int main() {
    int N, M;
    fin >> N >> M;

    vector<Muchie> muchii;
    muchii.reserve(M);

    // citim muchiile
    for (int i = 0; i < M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }

    // sortăm muchiile după cost
    sort(muchii.begin(), muchii.end(), [](Muchie &a, Muchie &b) {
        return a.cost < b.cost;
    });

    initializeaza_DSU(N);

    long long costTotal = 0;
    vector<pair<int, int>> rezultat;

    // Algoritmul lui Kruskal
    for (auto &m : muchii) {
        if (arbore(m.x, m.y)) {
            costTotal += m.cost;
            rezultat.push_back({m.x, m.y});
        }
    }

    // Scriem rezultatele în fișier
    fout << costTotal << "\n";
    fout << rezultat.size() << "\n";
    for (auto &e : rezultat)
        fout << e.first << " " << e.second << "\n";

    return 0;
}