#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

constexpr int N_MAX = 200000, M_MAX = 400000;

struct Edge {
    int x, y, cost;
    Edge() = default;
    Edge(const int& x_, const int& y_, const int& cost_) :
        x(x_), y(y_), cost(cost_) {}
    constexpr bool operator < (const Edge& b) const {
        return cost < b.cost;
    }
}edges[M_MAX];

int usedEdge[N_MAX];
int root[N_MAX + 1];

int findRoot(const int& x) {
    if (x == root[x]) {
        return x;
    }
    return root[x] = findRoot(root[x]);
}

void unite(const int& a, const int& b) {
    root[a] = root[b];
}

int main() {
    fin.tie(0);
    int n, m, totalCost = 0, cnt = 0;
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        fin >> x >> y >> cost;
        edges[i] = Edge(x, y, cost);
    }
    for (int i = 1; i <= n; ++i) {
        root[i] = i;
    }
    sort(edges, edges + m);

    for (int i = 0; i < m; ++i) {
        int root_x = findRoot(edges[i].x);
        int root_y = findRoot(edges[i].y);
        if (root_x != root_y) {
            totalCost += edges[i].cost;
            unite(root_x, root_y);
            usedEdge[cnt++] = i;
        }
    }
    fout << totalCost << '\n' << cnt << '\n';
    for (int i = 0; i < cnt; ++i) {
        fout << edges[usedEdge[i]].x << ' ' << edges[usedEdge[i]].y << '\n';
    }
}