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

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

const int N_MAX  = 2e5;

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

int n, m;
vector<Edge> edges;

int totalCost;
vector<Edge> ans;
int daddy[N_MAX + 2], depth[N_MAX + 2];

int root(int node) {
    while(node != daddy[node])
        node = daddy[node];

    return node;
}

void join(int rootX, int rootY) {
    if(depth[rootX] == depth[rootY]) {
        daddy[rootX] = rootY;
        depth[rootY]++;
    }

    if(depth[rootX] > depth[rootY])
        daddy[rootY] = daddy[rootX];

    if(depth[rootY] > depth[rootX])
        daddy[rootX] = daddy[rootY];
}

int main() {
    in >> n >> m;
    while(m--) {
        Edge cur;
        in >> cur.x >> cur.y >> cur.cost;

        edges.push_back(cur);
    }

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

    for(int i = 1; i <= n; i++) {
        daddy[i] = i;
        depth[i] = 1;
    }

    for(auto it: edges) {
        int rootX = root(it.x), rootY = root(it.y);

        if(rootX != rootY) {
            ans.push_back(it);
            totalCost += it.cost;
            join(rootX, rootY);
        }
    }

    out << totalCost << '\n' << ans.size() << '\n';
    for(auto it: ans)
        out << it.x << ' ' << it.y << '\n';

    return 0;
}