#include <bits/stdc++.h>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

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

void unionSets(vector<int>& parent, vector<int>& rank, int& a, int& b) {
    a = findSet(parent, a);
    b = findSet(parent, b);
    if(a != b) {
        if(rank[a] < rank[b])
            swap(a, b);
        parent[b] = a;
        if(rank[a] == rank[b])
            rank[a] = rank[a] + 1;
    }
}

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

int main() {
    int n, m, i, x, y, c, cost = 0;
    f >> n >> m;
    vector<Edge> edges(n + 1);
    vector<Edge> res;
    vector<int> parent(n + 1), rank(n + 1);

    for(i = 0; i < m; ++i) {
        f >> x >> y >> c;
        Edge e = Edge();
        e.node = x;
        e.to = y;
        e.w = c;
        edges.push_back(e);
    }

    for(i = 1; i <= n; ++i) {
        parent[i] = i;
        rank[i] = 0;
    }

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

    for(auto& e: edges) {
        if(findSet(parent, e.node) != findSet(parent, e.to)) {
            cost = cost + e.w;
            res.push_back(e);
            unionSets(parent, rank, e.node, e.to);
        }
    }

    g << cost << '\n' << res.size() << '\n';
    for(auto& e: res) {
        g << e.node << ' ' << e.to << '\n';
    }

    return 0;
}