#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

#define pair pair<int, int>

int n;
int T[200001];
long long suma;

vector<pair> drum;

struct muchie {
    int x, y, c;
} mch[400001];

bool csort(muchie a, muchie b) {
    if (a.c < b.c)
        return 1;
    return 0;
}

int Radacina(int x) {
    if (x == T[x]) return x;
    else return T[x] = Radacina(T[x]);
}

void Uneste(int x, int y) {
    if (T[x] > T[y]) T[x] = T[y];
    else T[y] = T[x];
} 


int main() {
    int i, m, x, y, r1, r2, nrc;

    ifstream f("apm.in");
    f >> n >> m;
    for (i = 1; i <= m; i++)
        f >> mch[i].x >> mch[i].y >> mch[i].c;
    f.close();

    for (i = 1; i <= n; i++)
        T[i] = i;
    
    sort(mch + 1, mch + m + 1, csort);

    nrc = 0;

    for (i = 1; i <= m && nrc < n; i++) {
        r1 = Radacina(mch[i].x), r2 = Radacina(mch[i].y);
        if (r1 != r2) {
            Uneste(r1, r2);
            suma += mch[i].c;
            drum.push_back({mch[i].x, mch[i].y});
            nrc++;
        }
    }

    ofstream g("apm.out");
    g << suma << '\n';
    g << drum.size() << '\n';
    for (i = 0; i < drum.size(); i++)
        g << drum[i].first << ' ' << drum[i].second << '\n';
    g.close();

    return 0;
}