#include <fstream>
#include <utility>
#include <climits>
#include <vector>
#include <bitset>

const int nMax = 2e5;

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

int main () {
    int n, m; fin >> n >> m;
    std::vector<std::vector<std::pair<int, int>>> graph(
            n, std::vector<std::pair<int, int>> ());
    while (m > 0) {
        int u, v, cost; fin >> u >> v >> cost; u -= 1, v -= 1;
        graph[u].emplace_back (std::make_pair (v, cost));
        graph[v].emplace_back (std::make_pair (u, cost));
        m -= 1;
    }


    int sumMin = 0;
    std::bitset<nMax> inTree;
    std::vector<int> distMin(n, INT_MAX);
    std::vector<std::pair<int, int>> edges;

    distMin[0] = 0;

    for (int i = 0; i < n; i += 1) {

        int Min = INT_MAX;

        int u;
        for (int w = 0; w < n; w += 1)
            if (!inTree[w] && distMin[w] < Min)
                Min = distMin[w], u = w;

        inTree[u] = true;
        sumMin += Min;

        int v;
        if (u != 0) {
            for (int j = 0; j < (int) graph[u].size (); j += 1)
                if (graph[u][j].second == Min) {
                    v = graph[u][j].first;
                    break;
                }
            edges.emplace_back (std::make_pair (u, v));
        }

        for (int j = 0; j < (int) graph[u].size (); j += 1)
            distMin[graph[u][j].first] = std::min (distMin[graph[u][j].first], graph[u][j].second);
    }


    fout << sumMin << '\n' << n - 1 << '\n';
    for (auto it : edges)
        fout << it.first + 1 << ' ' << it.second + 1 << '\n';
    return 0;
}