#include <fstream>
#include <queue>

using namespace std;

const int NMAX = 200001;

struct muchie {
    int x, y, cost;
};
muchie rez[NMAX];

bool operator< (const muchie& m1, const muchie& m2) {
    return m1.cost > m2.cost;
}

int N, M, COST;
int GR[NMAX];

priority_queue<muchie, vector<muchie>> Q;

void citire() {
    ifstream in ("apm.in");
    in >> N >> M;
    muchie m;
    for(int i = 1; i <= M; i++) {
        in >> m.x >> m.y >> m.cost;
        Q.push(m);
    }

    in.close();
}

int find (int x) {
    int R, y;
    for (R = x; GR[R] != R; R = GR[R]);

    for (; GR[x] != x;) {
        y = GR[x];
        GR[x] = R;
        x = y;
    }
    return R;
}

void unite(int grn1, int grn2) {
    GR[grn2] = grn1;
}

void kruskal(int n) { //cu multimi disjuncte
    for(int i = 1; i <= n; i++)
        GR[i] = i;
    COST = 0;
    for(; n > 1;) {
        muchie m = Q.top();
        Q.pop();
        int grn1 = find(m.x), grn2 = find(m.y);
        if(grn1 != grn2) {
            rez[n - 1] = m;
            COST += m.cost;
            unite(grn1, grn2);
            n--;
        }
    }
}

void afisare() {
    ofstream out("apm.out");
    out << COST << '\n' << N - 1 << '\n';
    for(int i = 1; i < N; i++)
        out << rez[i].x << ' ' << rez[i].y << '\n';
    out.close();
}

int main() {
    citire();
    kruskal(N);
    afisare();
    return 0;
}