#include <stdio.h>
#include <vector>
#include <algorithm>

#define maxn 200005

using namespace std;

int n, m;
vector<pair<int, pair<int, int>>> edges;
int T[maxn];

int get_root(int x) {
    int root = x;
    while (T[root] > 0) {
        root = T[root];
    }

    while (x != root) {
        int t = T[x];
        T[x] = root;
        x = t;
    }

    return root;
}

bool join(int x, int y) {
    int root_x = get_root(x);
    int root_y = get_root(y);

    if (root_x == root_y) {
        return false;
    }

    if (T[root_x] <= T[root_y]) {
        T[root_x] += T[root_y];
        T[root_y] = root_x;
    } else {
        T[root_y] += T[root_x];
        T[root_x] = root_y;
    }

    return true;
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y, c; scanf("%d %d %d", &x, &y, &c);
        edges.push_back(make_pair(c, make_pair(x, y)));
    }

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

    for (int i = 1; i <= n; ++i) {
        T[i] = -1;
    }

    int total = 0;
    vector<pair<int, int>> sol;
    for (int i = 0; i < (int) edges.size(); ++i) {
        int cost = edges[i].first;
        int x = edges[i].second.first;
        int y = edges[i].second.second;

        if (join(x, y)) {
            total += cost;
            sol.push_back(make_pair(x, y));
        }
    }

    printf("%d\n", total);
    printf("%d\n", (int) sol.size());
    for (int i = 0; i < (int) sol.size(); ++i) {
        printf("%d %d\n", sol[i].first, sol[i].second);
    }

    return 0;
}