#include <iostream>
#include <fstream>
#define NMaxVf 200005
#define NMaxMuchii 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {
    int x, y, cost;
};

muchie gr[NMaxMuchii];
int a[NMaxVf], c[NMaxVf];
int n, m, costAPM, nrM;

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> gr[i].x >> gr[i].y >> gr[i].cost;
    for (int i = 1; i <= n; i++)
        c[i] = i;
}

void show() {
    fout << costAPM << "\n" << nrM << "\n";
    for (int i = 1; i <= nrM; i++) {
        fout << gr[a[i]].y << " " << gr[a[i]].x << "\n";
        costAPM += gr[a[i]].cost;
    }
}

void sortMuchii(int st, int dr) {
    muchie t;
    int i, j;
    if (st < dr) {
        t = gr[st];
        i = st;
        j = dr;
        while (i < j) {
            while (i < j && gr[j].cost >= t.cost)
                j--;
            gr[i] = gr[j];
            while (i < j && gr[i].cost <= t.cost)
                i++;
            gr[j] = gr[i];
        }
        gr[i] = t;
        sortMuchii(st, i - 1);
        sortMuchii(i + 1, dr);
    }
}

int main() {
    int minim, maxim, nrMSel = 0;
    read();
    sortMuchii(1, m);
    for (int i = 1; nrMSel < n - 1; i++)
        if (c[gr[i].x] != c[gr[i].y]) {
            a[++nrMSel] = i;
            costAPM += gr[i].cost;
            nrM++;
            if (c[gr[i].x] < c[gr[i].y]) {
                minim = c[gr[i].x];
                maxim = c[gr[i].y];
            }
            else {
                minim = c[gr[i].y];
                maxim = c[gr[i].x];
            }
            for (int j = 1; j <= n; j++)
                if (c[j] == maxim)
                    c[j] = minim;
        }
    show();
}