#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

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

struct Muchie {
    int u, v, cost;
    bool operator>(const Muchie& m) const {
        return cost > m.cost;
    }
};

struct Nod {
    int v, cost;
    bool operator>(const Nod& n) const {
        return cost > n.cost;
    }
};

int main() {
    int n, m;
    f >> n >> m;

    vector<vector<pair<int, int>>> graf(n);
    vector<int> tata(n, -1), d(n, INT_MAX);
    vector<bool> inArbore(n, false);

    // Citim muchiile
    for (int i = 0; i < m; i++) {
        int x, y, c;
        f >> x >> y >> c;
        x--; y--; // Reducem 1 pentru a trece la indexare de la 0
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
    }

    // Folosim un heap pentru a selecta nodul cu costul minim
    priority_queue<Nod, vector<Nod>, greater<Nod>> pq;
    d[0] = 0;
    pq.push({0, 0}); // Incepem de la nodul 0

    int cost_total = 0;
    vector<Muchie> solutie;

    while (!pq.empty()) {
        Nod nod = pq.top();
        pq.pop();

        int u = nod.v;
        int cost = nod.cost;

        if (inArbore[u]) continue; // Daca nodul este deja in arbore, il ignoram
        inArbore[u] = true; // Adaugam nodul in arbore
        cost_total += cost;

        // Actualizam muchiile care se adauga in arbore
        if (tata[u] != -1) {
            solutie.push_back({tata[u], u, cost});
        }

        // Actualizam vecinii
        for (auto& vecin : graf[u]) {
            int v = vecin.first;
            int pret = vecin.second;
            if (!inArbore[v] && pret < d[v]) {
                d[v] = pret;
                tata[v] = u;
                pq.push({v, pret});
            }
        }
    }

    // Afisare rezultat
    g << cost_total << endl;
    g << solutie.size() << endl;
    for (const auto& m : solutie) {
        g << m.u + 1 << " " << m.v + 1 << endl;
    }

    return 0;
}