/// Craciun Catalin
///  APM - Arbori partiali de cost minim
#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 index[NMax];
int X[NMax], Y[NMax], C[NMax];
int FA[NMax], GR[NMax]; /// Folosite pentru paduri de multimi disjuncte
vector<int> sol;
long long cost = 0;

int rootFor(int x) {

    int e, aux;
    for (e = x; FA[e]!=e; e = FA[e]);

    /// Compresia drumurilor
    for (;FA[x]!=x;) {
        aux = FA[x];
        FA[x] = e;
        x = aux;
    }

    return e;
}

int makeTree(int x, int y) {

    int firstRoot = rootFor(x);
    int secondRoot = rootFor(y);

    if (GR[firstRoot] > GR[secondRoot]) {
        FA[secondRoot] = firstRoot;
    } else if (GR[secondRoot] > GR[firstRoot]) {
        FA[firstRoot] = secondRoot;
    } else {
        FA[secondRoot] = firstRoot;
        GR[firstRoot]++;
    }
}

bool compare(int i, int j) {

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

int main() {

    f>>n>>m;
    for (int i=1;i<=n;i++) GR[i] = 1, FA[i]=i;
    for (int i=1;i<=m;i++) {
        f>>X[i]>>Y[i]>>C[i];
        index[i] = i;
    }

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

    int number = n;
    for (int i=1;i<=m;i++) {
        int nod1 = X[index[i]];
        int nod2 = Y[index[i]];

        if (rootFor(nod1) != rootFor(nod2)) {
            cost += C[index[i]];
            sol.push_back(index[i]);
            makeTree(nod1, nod2);
            number--;
        }
        if (number == 1)
            break;
    }

    g<<cost<<'\n'<<n-1<<'\n';
    for (int i=0;i<n-1;i++)
        g<<X[sol[i]]<<' '<<Y[sol[i]]<<'\n';

    f.close(); g.close();

    return 0;
}