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

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

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

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

int indMinVal(int i) {
    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);
        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);
    }
}

void update (int a, int b) {
    int i;

    for (i = 1; i <= n; i++)
        if (p[i] == a)
            p[i] = b;
}

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++)
        p[i] = INT_MAX;

    heapSort(n);
    i = 2;
    a.push_back(1);
    p[v[1].x] = p[v[1].y] = min (v[1].x, v[1].y);
    while (a.size() < n) {
        if (p[v[i].x] != p[v[i].y] || !p[v[i].x]) {
            a.push_back(i);
            cost += v[i].c;
            if (p[v[i].x] == INT_MAX && p[v[i].y] == INT_MAX)
                p[v[i].x] = p[v[i].y] = min (v[i].x, v[i].y);
            else if (min(p[v[i].x], p[v[i].y]) == p[v[i].x])
                    update (p[v[i].y], p[v[i].x]);
                else update (p[v[i].x], p[v[i].y]);
        }
    }

    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;
}