#include <fstream>
#define NMaxVf 50
#define NMaxMuchii NMaxVf * (NMaxVf - 1) / 2


struct Muchie {
    int e1, e2, cost;
};


Muchie G[NMaxMuchii];
int A[NMaxVf], c[NMaxVf];
int n, m;


void initializare() {
    std::ifstream fin("apm.in");
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> G[i].e1 >> G[i].e2 >> G[i].cost;
    }
    for (int i = 1; i <= n; i++) {
        c[i] = i;
    }
    fin.close();
}

void afisare() {
    std::ofstream fout("apm.out");
    int costAPM = 0;
    for (int i = 1; i < n; i++) {
        costAPM += G[A[i]].cost;
    }
    fout << costAPM << "\n" << n - 1 << "\n";
    for (int i = 1; i < n; i++) {
        fout << G[A[i]].e1 << " " << G[A[i]].e2 << "\n";
    }
}

void sortareMuchii (int st, int dr) {
    int i, j;
    Muchie x;
    if (st < dr) {
        x = G[st];
        i = st;
        j = dr;
        while (i < j) {
            while (i < j && G[j].cost >= x.cost) {
                j--;
            }
            G[i] = G[j];
            while (i < j && G[i].cost <= x.cost) {
                i++;
            }
            G[j] = G[i];
        }
        G[i] = x;
        sortareMuchii(st, i - 1);
        sortareMuchii(i + 1, dr);
    }
}

int main(int argc, char *argv[]) {
    int i, j, minim, maxim, NrMSel;
    initializare();
    sortareMuchii(1, m);
    NrMSel = 0;
    for (i = 1; NrMSel < n - 1; i++) {
        if (c[G[i].e1] != c[G[i].e2]) {
            A[++NrMSel] = i;
        }
        if (c[G[i].e1] < c[G[i].e2]) {
            minim = c[G[i].e1];
            maxim = c[G[i].e2];
        } else {
            maxim = c[G[i].e1];
            minim = c[G[i].e2];
        }
        for (j = 1; j <= n; j++) {
            if (c[j] == maxim) {
                c[j] = minim;
            }
        }
        afisare();
    }
    return 0;
}