#include <bits/stdc++.h>
using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

int N, M, cost, nrm;
int p[200001], rnk[200001];
struct muchie {
    int a, b;
    int c;
};
vector<muchie> solutie;



bool operator < (muchie x, muchie y){
    return x.c > y.c;
}

priority_queue<muchie> q;

void citire() {
    fi >> N >> M;
    muchie x;
    for(int i = 0; i < M; i++) {
        fi >> x.a >> x.b >> x.c;
        q.push(x);
    }
}

int parinte(int nod) {
    if(p[nod] == 0)
        return nod;
    p[nod] = parinte(p[nod]);
    return p[nod];
}

void kruskal() {
    while(!q.empty()) {
        muchie x = q.top();
        q.pop();
        int aa, bb;
        aa = parinte(x.a);
        bb = parinte(x.b);
        if(aa != bb) {
            cost += x.c;
            if(rnk[aa] < rnk[bb])
                swap(aa, bb);
            p[bb] = aa;
            rnk[aa] += rnk[bb] + 1;
            solutie.push_back(x);
            nrm++;
        }
    }
}

int main() {
    citire();
    kruskal();
    fo << cost << "\n" << nrm << "\n";
    for(auto it : solutie) {
        fo << it.a << " " << it.b << "\n";
    }
    return 0;
}