#include <iostream>
#include <fstream>
#include <deque>
#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");

deque<muchie> graf;
deque<muchie> apm;
int conv[200003];

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);

    for(int i = 1; i <= n; i++)
        conv[i] = i;

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

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

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

        if(conv[n1] != conv[n2]) {

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

            for(int j = 1; j <= n; j++)
                if(conv[j] == aux)
                    conv[j] = conv[n1];

        }

    }

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

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

    return 0;
}