#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int x, y, c;
    bool operator<(const Edge& other) const {
        return c < other.c;
    }
};

int parent[200001], sz[200001];

int find(int u) {
    while (u != parent[u]) {
        parent[u] = parent[parent[u]];
        u = parent[u];
    }
    return u;
}

void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    parent[v] = u;
    sz[u] += sz[v];
}

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].x >> edges[i].y >> edges[i].c;
    }

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

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

    long long totalCost = 0;
    vector<pair<int,int>> mstEdges;

    for (const Edge& e : edges) {
        int u = e.x, v = e.y;
        if (find(u) != find(v)) {
            unite(u, v);
            totalCost += e.c;
            mstEdges.push_back({u, v});
            if ((int)mstEdges.size() == N - 1) break;
        }
    }

    fout << totalCost << "\n";
    fout << mstEdges.size() << "\n";
    for (auto& p : mstEdges) {
        fout << p.first << " " << p.second << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}