#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; inTree[0] = true;
    std::vector<std::pair<int, int>> edges;

    for (int i = 0; i < n - 1; i += 1) {
        int Min = INT_MAX, u, v;

        for (int x = 0; x < n; x += 1)
            for (int j = 0; j < (int) graph[x].size (); j += 1) {

                int y = graph[x][j].first;
                int cost = graph[x][j].second;

                if (inTree[x] && !inTree[y] && cost < Min)
                    Min = cost, u = x, v = y;
            }

        sumMin += Min;
        inTree[v] = true;
        edges.emplace_back (std::make_pair (u, v));
    }

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