#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct muchie {
    int nod1;
    int nod2;
    int cost;
};

bool cmp(muchie a, muchie b) {
    return a.cost < b.cost;
}

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

vector<muchie> graf;
vector<muchie> apm;
int T[200003];
int H[200003];

int root(int nod) {

    while(T[nod] != 0)
        nod = T[nod];

    return nod;

}

int main() {

    int n,m;
    muchie temp;
    in >> n >> m;

    for(int i = 0; i < m; i++) {

        in >> temp.nod1 >> temp.nod2 >> temp.cost;
        graf.push_back(temp);

    }

    sort(graf.begin(), graf.end(), cmp);

    int n1,n2,aux,r1,r2;
    int sum = 0;

    for(int i = 0; i < m; i++) {

        n1 = graf[i].nod1;
        n2 = graf[i].nod2;

        r1 = root(n1);
        r2 = root(n2);

        if(r1 != r2) {

            apm.push_back(graf[i]);
            sum += graf[i].cost;
            if(apm.size() == n-1)
                break;

            if(H[r1] > H[r2]) {

                T[r2] = r1;

            } else if(H[r1] < H[r2]) {

                T[r1] = r2;

            } else {

                T[r2] = r1;
                H[r2]++;

            }

        }

    }

    out << sum << '\n' << apm.size() << '\n';

    for(int i = 0; i < apm.size(); i++)
        out << apm[i].nod1 << " " << apm[i].nod2 << '\n';

    return 0;
}