#include <bits/stdc++.h>

using namespace std;

int roots[400001];

int getRoot(int x) {
    if (roots[x] == 0 || roots[x] == x) return x;
    return roots[x] = getRoot(roots[x]);
}

void join(int x, int y) {
    roots[getRoot(x)] = getRoot(y);
}

bool check(int x, int y) {
    return getRoot(x) == getRoot(y);
}

struct edge {
    int x;
    int y;
    int cost;

    bool operator<(const edge& rhs) const {
        return this->cost < rhs.cost;
    }
};
vector<edge> edges;

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

    int n, m;
    cin >> n >> m;
    edges.reserve(m);
    for (int i = 0, x, y, z; i < m; i++) {
        cin >> x>>y>>z;
        edge e;
        e.x = x;
        e.y = y;
        e.cost = z;
        edges.push_back(e);
    }

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

    int edges_count = 0;
    int min_cost = 0;
    vector<edge> solution;
    solution.reserve(n - 1);
    for (int i = 0; i < m && edges_count != n - 1; i++) {
        if (!check(edges[i].x, edges[i].y)) {
            min_cost += edges[i].cost;
            join(edges[i].x, edges[i].y);
            edges_count++;
            solution.push_back(edges[i]);
        }
    }

    cout << min_cost << "\n";
    cout << n - 1 << "\n";
    for (int i = 0; i < n - 1; i++) {
        cout << solution[i].x << " " << solution[i].y << "\n";
    }

    return 0;
}