#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> parent;

void read(int &n, int &m, vector<pair<int, pair<int, int> > > &edges) {
    int source, target, cost;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &source, &target, &cost);
        edges.push_back(make_pair(cost, make_pair(source - 1, target - 1)));
    }
}

int find_parent(int node) {
    if (node != parent[node]) {
        parent[node] = find_parent(parent[node]);
    }
    return parent[node];
}

pair<pair<int, int>, vector<pair<int, int> > > solve(vector<pair<int, pair<int, int> > > edges, int n) {
    int total_cost = 0;
    int number_of_edges = 0;
    vector<pair<int, int> > used_edges;

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

    for (int i = 0; i < n; i++) {
        parent.push_back(i);
    }

    for (vector<pair<int, pair<int, int> > >::iterator it = edges.begin(); it != edges.end(); it++) {
        if (number_of_edges == n - 1){
            break;
        }

        if (find_parent(it->second.first) != find_parent(it->second.second)) {
            parent[find_parent(it->second.first)] = find_parent(it->second.second);
            used_edges.push_back(it->second);
            total_cost += it->first;
            number_of_edges++;
        }
    }

    return make_pair(make_pair(total_cost, number_of_edges), used_edges);
}

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

    int n, m;
    vector<pair<int, pair<int, int> > > edges;
    pair<pair<int, int>, vector<pair<int, int> > > solution;

    read(n, m, edges);
    solution = solve(edges, n);

    printf("%d\n%d\n", solution.first.first, solution.first.second);

    for (vector<pair<int, int> >::iterator it = solution.second.begin(); it != solution.second.end(); it++) {
        printf("%d %d\n", it->first + 1, it->second + 1);
    }
}