#include <fstream>
#include <vector>
#include <climits>

#define NMAX 200001
using namespace std;

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

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

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 rep(int nod) {
    int s = nod, next;

    for (nod; T[nod] != nod; nod = T[nod]);

    while (s != T[s]) {
        next = T[s];
        T[s] = nod;
        s = next;
    }

    return nod;
}

void reuniune(int x, int y) {
    int a, b;

    a = rep(x);
    b = rep(y);

    if (H[a] == H[b]) {
        T[a] = b;
        H[b]++;
    }
    else if (H[a] < H[b])
            T[a] = b;
        else T[b] = a;
}

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 ();

    for (i = 1; i <= n; i++)
        T[i] = i;

    heapSort(m);
    i = 1;
    a.push_back(0);
    while (a.size() != n) {
        if (rep(v[i].x) != rep(v[i].y)) {
            a.push_back(i);
            cost += v[i].c;
            reuniune(v[i].x, v[i].y);
        }
        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;
}