#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct edge {
    int v1, v2, c;
};

typedef pair<int, int> Pair;

int n, m, Min;
vector<int> forest;
vector<vector<Pair>> neigh;
vector<edge> edges;
vector<Pair> result;

int grupa(int i){
    if (forest[i] == i) return i;
    forest[i] = grupa(forest[i]);
    return forest[i];
}

struct compare {
    bool operator()(const edge x, const edge y) {
        return (x.c) < (y.c);
    }
};

void read() {
    int v1, v2, c;
    scanf("%d%d", &n, &m);
    neigh.resize(n);
    forest.resize(n);
    edges.resize(m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &v1, &v2, &c);
        //neigh[v1].push_back(Pair(v2, c));
        //neigh[v2].push_back(Pair(v1, c));
        edges[i] = edge({v1-1, v2-1, c});
    }
    for (int i = 0; i < n; ++i) {
        forest[i] = i;
    }
}

void solve() {
    sort(edges.begin(), edges.end(), compare());
    for (int i = 0; i < m; ++i) {
        if (grupa(edges[i].v1) != grupa(edges[i].v2)) {
            forest[forest[edges[i].v1]] = forest[forest[edges[i].v2]];
            Min += edges[i].c;
            result.push_back(Pair(edges[i].v1, edges[i].v2));
        }
    }
}

void write() {
    printf("%d\n%d\n", Min, result.size());
    for (unsigned i = 0; i < result.size(); ++i) {
        printf("%d %d\n", result[i].first + 1, result[i].second + 1);
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    read();
    solve();
    write();
    return 0;
}