#include <fstream>
#include <vector>
#include <climits>
using namespace std;

struct arc {int x, y, c;};

vector<arc> v;
vector<int> a;
int n, m, T[200005], H[200005], cost;

void schimb (int a, int b) {
    arc c = v[a];
    v[a] = v[b];
    v[b] = c;
}

int indMinVal(int i,int n) {
    if (i*2+1 <= n)
        if (v[i*2].c > v[i*2+1].c)
            return i*2;
        else return i*2+1;
    else return i*2;
}

void promovare (int i, int n) {
    int ind;

    if (i <= n/2) {
        ind = indMinVal(i, n);
        if (v[i].c < v[ind].c) {
            schimb (i, ind);
            promovare (ind, n);
        }
    }
}

void minHeap(int n) {
    int i;

    for (i = n/2; i >= 1; i--)
        promovare(i, n);
}

void heapSort(int n) {
    int i;

    minHeap(n);
    for (i = n; i >= 1; i--) {
        schimb (1, i);
        promovare (1, i-1);
    }
}

int Arb(int nod) {
    while (T[nod])
        nod = T[nod];
    return nod;
}

int main() {
    int i;
    arc z;

    ifstream in ("apm.in");
    in >> n >> m;
    z.x = z.y = z.c = 0;
    v.push_back(z);
    for (i = 1; i <= m; i++) {
        in >> z.x >> z.y >> z.c;
        v.push_back(z);
    }
    in.close ();

    heapSort(m);
    i = 1;
    a.push_back(0);
    while (a.size() < n) {
        while (Arb(v[i].x) == Arb(v[i].y))
            i++;
        a.push_back(i);
        cost += v[i].c;
        if (H[v[i].x] == H[v[i].y]) {
            if (!H[v[i].x])
                H[v[i].y] = 1;
            else H[v[i].y] = max(H[v[i].x], H[v[i].y]);
            T[v[i].x] = v[i].y;
        }
        else if (H[v[i].x] < H[v[i].y])
                T[v[i].x] = v[i].y;
            else T[v[i].y] = v[i].x;
        i++;
    }

    ofstream out ("apm.out");
    out << cost << '\n' << n-1 << '\n';
    for (i = 1; i <= n - 1; i++)
        out << v[a[i]].x << ' ' << v[a[i]].y << '\n';
    out.close();

    return 0;
}