#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out")
/*
Fisierul grafpond.in are urmatoarea structura: numarul de varfuri n, numarul de muchii m
si lista muchiilor cu costul lor (o muchie fiind data prin extremitatile sale si cost).
Costul unei muchii este numar intreg.
5 7
1 4 1
1 3 5
1 2 10
2 3 2
4 2 6
4 5 12
5 2 11
*/
/*
Implementati algoritmul lui Kruskal pentru determinarea unui arbore partial de cost minim
 al unui graf conex ponderat cu n varfuri si m muchii. Graful se va citi din fisierul grafpond.in.
*/

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

vector<int> parinte, nivel;
vector<Muchie> result;

void creaza_multime(int v) {
    parinte[v] = v;
    nivel[v] = 0;
}

int gaseste_multime(int v) {
    if (v == parinte[v])
        return v;
    return parinte[v] = gaseste_multime(parinte[v]);
}

void reuniune(int a, int b) { // Union sets
    a = gaseste_multime(a);
    b = gaseste_multime(b);
    if (a != b) {
        if (nivel[a] < nivel[b])
            swap(a, b);
        parinte[b] = a;
        if (nivel[a] == nivel[b])
            nivel[a]++;
    }
}

int kruskal(int n, vector<Muchie>& muchii) {
    parinte.resize(n);
    nivel.resize(n);
    for (int i = 0; i < n; i++)
        creaza_multime(i);

    sort(muchii.begin(), muchii.end());

    int cost = 0;

    for (Muchie e : muchii) {
        if (gaseste_multime(e.u) != gaseste_multime(e.v)) {
            cost += e.pret;
            result.push_back(e);
            reuniune(e.u, e.v);
        }
    }

    return cost;
}

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

    vector<Muchie> muchii;
    for (int i = 0; i < m; i++) {
        int u, v, pret;
        f >> u >> v >> pret;
        muchii.push_back({u - 1, v - 1, pret}); // Scad 1 pentru a trece la indexare de la 0
    }
    f.close();

    int min_cost = kruskal(n, muchii);
    cout << min_cost << endl;

    cout << result.size() << endl;
    for (Muchie e : result) {
        cout << e.u + 1 << " " << e.v + 1 << endl;
    }

    return 0;
}