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

using namespace std;

struct Edge {
    int x;
    int y;
    int c;
};
int parent[200001];
int rnk[200001];

int Find(int x) {

    if (parent[x] == x) {
        return x;
    }
    parent[x] = Find(parent[x]);
    return parent[x];
}


void Unite(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a == b) {
        return;
    }

    if (rnk[a] < rnk[b]) {
        parent[a] = b;
    } else if (rnk[a] > rnk[b]) {
        parent[b] = a;
    } else {
        parent[b] = a;
        rnk[a]++;
    }
}

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

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

    vector<Edge> edges;
    edges.reserve(M);

    for (int i = 0; i < M; i++) {
        Edge e;
        fin >> e.x >> e.y >> e.c;
        edges.push_back(e);
    }

    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        rnk[i] = 0;
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.c < b.c;
    });

    long long totalCost = 0;                    
    vector<pair<int,int>> solutionEdges;         
    solutionEdges.reserve(N - 1);

    for (int i = 0; i < M; i++) {
        int x = edges[i].x;
        int y = edges[i].y;
        int c = edges[i].c;

        int rootX = Find(x);
        int rootY = Find(y);

        if (rootX != rootY) {
            totalCost += c;
            solutionEdges.push_back({x, y});
            Unite(rootX, rootY);
        }
        if ((int)solutionEdges.size() == N - 1) {
            break;
        }
    }
    fout << totalCost << "\n";
    fout << solutionEdges.size() << "\n";
    for (size_t i = 0; i < solutionEdges.size(); i++) {
        fout << solutionEdges[i].second << " " << solutionEdges[i].first << "\n";
    }

    return 0;
}