/// Craciun Catalin
///  APM
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define NMax 200005

using namespace std;

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

int n, m;
int X[NMax], Y[NMax], C[NMax];
vector< pair<int, int> > sol;
int index[NMax];
long long cost = 0;
int father[NMax], height[NMax]; /// Paduri de multimi distincte, tata si adancime arbore

void joinElements(int i, int j) {

    int fatherOfI = father[i];
    int fatherOfJ = father[j];

    if (height[fatherOfI] >  height[fatherOfJ]) {
        father[fatherOfJ] = fatherOfI;
    } else if (height[fatherOfI] < height[fatherOfJ]) {
        father[fatherOfI] = fatherOfJ;
    } else {
        father[fatherOfJ] = fatherOfI;
        height[fatherOfI]++;
    }
}

int fatherOf(int pos) {

    int aux2, aux;
    for (aux = pos; father[aux] != aux; aux = father[aux]);
    for (aux2 = pos; father[aux2] != aux2; ) {
        int x = father[aux2];
        father[aux2] = aux;
        aux2 = x;
    }

    return aux;
}

bool cmp(int i, int j) {

    if (C[i] < C[j])
        return true;
    return false;
}

void read() {

    f>>n>>m;
    for (int i=1;i<=m;i++) {
        index[i] = i;
        father[i] = i;
        height[i] = 1;
        int x,y,c;
        f>>x>>y>>c;
        X[i] = x;
        Y[i] = y;
        C[i] = c;
    }

    sort(index+1, index+m+1, cmp);

    f.close();
}

void findAPM() {

    int muchii = n;
    for (int i=1;i<=m;i++) {
        if (fatherOf(X[index[i]]) != fatherOf(Y[index[i]])) {
            cost+=C[index[i]];
            sol.push_back(make_pair(X[index[i]], Y[index[i]]));
            muchii--;
            joinElements(X[index[i]], Y[index[i]]);
        }
        if (muchii == 1)
            break;
    }

    g<<cost<<'\n'<<sol.size()<<'\n';
    for (int i=0;i<sol.size();i++) {
        g<<sol[i].first<<' '<<sol[i].second<<'\n';
    }

    g.close();
}

int main() {

    read();
    findAPM();

    return 0;
}