#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int n, m, op, x, y, c;

class edge {
public:
    int x, y;
    int c;

    bool operator<(const edge &other) {
        return c < other.c;
    }
};
int Find(int x, vector<int> &p) {
    int r = x;
    while (r != p[r]) {
        r = p[r];
    }

    while (p[x] != x) {
        int temp = p[x];
        p[x] = r;
        x = temp;
    }

    return r;
}

void Union(int x, int y, vector<int> &p, vector<int> &r) {
    int rx = Find(x, p);
    int ry = Find(y, p);

    if (r[rx] < r[ry]) {
        p[rx] = ry;
    } else {
        p[ry] = rx;
    }

    if (r[rx] == r[ry]) {
        r[ry]++;
    }
}

void kruskal(vector<edge> &edges, int &sum, vector<pair<int, int>> &ans, int n, vector<int> &p, vector<int>r) {
    int k = 0;

    for (auto edge : edges) {
        int rx = Find(edge.x, p);
        int ry = Find(edge.y, p);
        if (rx != ry) {
            k++;
            sum += edge.c;
            ans.push_back({edge.x, edge.y});
            Union(edge.x, edge.y, p, r);
        }

        if (k == n - 1) {
            break;
        }
    }
}

int main() {
    in >> n >> m;
    vector<int> p(n + 1, 0);
    vector<int> r(n + 1, 1);

    for (int i = 1; i <= n; i++)
        p[i] = i;

    vector<edge> edges;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        edges.push_back({x, y, c});
    }

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

    int sum = 0;
    vector<pair<int, int>> ans;

    kruskal(edges, sum, ans, n, p, r);

    out << sum << '\n';
    out << ans.size() << '\n';
    for (auto it : ans) {
        out << it.first << " " << it.second << '\n';
    }

    return 0;
}