/// 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];
int father[NMax], height[NMax]; /// Paduri de multimi distincte, tata si adancime arbore

void joinElements(int i, int j) {

    if (height[i] >  height[j]) {
        father[j] = i;
    } else if (height[i] < height[j]) {
        father[i] = j;
    } else {
        father[j] = i;
        height[i]++;
    }
}

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