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

using namespace std;

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

int find(int node, vector<int>& parent) {
    if (parent[node] != node) {
        parent[node] = find(parent[node], parent);
    }
    return parent[node];
}

void unite(int u, int v, vector<int>& parent, vector<int>& rank) {
    int root_u = find(u, parent);
    int root_v = find(v, parent);
    if (root_u != root_v) {
        if (rank[root_u] < rank[root_v]) {
            parent[root_u] = root_v;
        } else if (rank[root_u] > rank[root_v]) {
            parent[root_v] = root_u;
        } else {
            parent[root_v] = root_u;
            rank[root_u]++;
        }
    }
}

int main() {
    ifstream fin("test.in");
    ofstream fout("test.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].cost;
    }

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

    vector<int> parent(N + 1), rank(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    int mst_cost = 0;
    vector<pair<int, int>> mst_edges;

    for (const auto& edge : edges) {
        if (find(edge.x, parent) != find(edge.y, parent)) {
            mst_cost += edge.cost;
            mst_edges.push_back({edge.x, edge.y});
            unite(edge.x, edge.y, parent, rank);
        }
    }

    fout << mst_cost << "\n";
    fout << mst_edges.size() << "\n";
    for (const auto& [x, y] : mst_edges) {
        fout << x << " " << y << "\n";
    }

    return 0;
}