#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Edge {
    int from, to, cost;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

int find(vector<int>& parent, int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

void unionSet(vector<int>& parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    if (xset != yset)
        parent[xset] = yset;
}

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

    int N, M;
    fin >> N >> M;

    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        fin >> edges[i].from >> edges[i].to >> edges[i].cost;
        edges[i].from--;
        edges[i].to--;
    }

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

    vector<int> parent(N, -1);
    int cost = 0;
    int numEdges = 0;

    for (const auto& edge : edges) {
        int x = find(parent, edge.from);
        int y = find(parent, edge.to);

        if (x != y) {
            unionSet(parent, x, y);
            cost += edge.cost;
            numEdges++;
        }
    }

    fout << cost << endl;
    fout << numEdges << endl;

    for (int i = 0; i < N - 1; ++i) {
        int j = 0;
        while (find(parent, edges[j].from) != find(parent, edges[j].to)) {
            j++;
        }
        fout << edges[j].from + 1 << " " << edges[j].to + 1 << endl;
        unionSet(parent, edges[j].from, edges[j].to);
    }

    return 0;
}