#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

#define MAX_N 200005

using namespace std;

vector<tuple<int, int, int> > edges;
int root[MAX_N];
int siz[MAX_N];

int getRoot(int pos)
{
    while (root[pos] != pos) {
        root[pos] = root[root[pos]];
        pos = root[pos];
    }
    return pos;
}

void unite(int x, int y)
{
    x = getRoot(x);
    y = getRoot(y);
    if (siz[x] > siz[y]) {
        root[y] = x;
        siz[x] += siz[y];
    } else {
        root[x] = y;
        siz[y] += siz[x];
    }
}

int main()
{
    FILE *fin = fopen("apm.in", "r");
    FILE *fout = fopen("apm.out", "w");
    int n, m;
    fscanf(fin, "%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        fscanf(fin, "%d %d %d", &a, &b, &c);
        a--; b--;
        edges.push_back({c, a, b});
    }
    for (int i = 0; i < n; i++) {
        root[i] = i;
        siz[i] = 1;
    }
    sort(edges.begin(), edges.end());
    vector<pair<int, int> > result;
    int total = 0;
    for (auto j: edges) {
        int first = get<2>(j);
        int second = get<1>(j);
        int cost = get<0>(j);
        if (getRoot(first) != getRoot(second)) {
            unite(first, second);
            result.push_back({first, second});
            total += cost;
        }
    }
    fprintf(fout, "%d\r\n", total);
    fprintf(fout, "%lu\r\n", result.size());
    for (auto j: result)
        fprintf(fout, "%d %d\r\n", j.first + 1, j.second + 1);
}