#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <fstream>
#include <utility>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct e {
    int u, v, cost;
};

int n, m, c, x, y, p[100005], h[100005], sol;
vector <pair<int, int>> M;
vector <e> L;
int Find (int x) {
    while (x != p[x]) {
        x = p[x];
    }
    return x;
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (h[x] < h[y]) {
        p[x] = y;
    }
    else {
        if (h[x] > h[y]) {
            p[y] = x;
        }
        else {
            p[x] = y;
            h[y]++;
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        fin >> x >> y >> c;
        L.push_back({x, y, c});
    }
    sort(L.begin(), L.end(), [](const e& a, const e& b) {
    return a.cost < b.cost;
});
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        h[i] = 1;
    }

    for (const auto& muchie : L) {
        if (Find(muchie.u) != Find(muchie.v)) {
            sol += muchie.cost;
            M.push_back({muchie.u, muchie.v});
            Union(muchie.u, muchie.v);
        }
    }
    fout << sol << "\n";
    fout << M.size() << "\n";
    for (int i = 0; i < M.size(); i++) {
        cout << M[i].first << " " << M[i].second << "\n";
    }
}