#include <bits/stdc++.h>
using namespace std;

const int nmax = 2e5 + 5, mmax = 4e5 + 5;

int N, M, t[nmax], h[nmax], cost, cnt;
typedef struct poz2 {
    int a, b;
} student2;
vector<student2> ans;

typedef struct poz {
    int a, b, c;
} student;
student v[mmax];

ifstream fin("apm.in");
ofstream fout("apm.out");

bool comp(student x, student y) {
    return x.c < y.c;  // Strict ordering
}

int Radacina(int node) {
    if (t[node] == node) return node;
    return t[node] = Radacina(t[node]);  // Path compression
}

void Unire(int a, int b) {
    a = Radacina(a);
    b = Radacina(b);
    if (a != b) {
        if (h[a] > h[b]) {
            t[b] = a;
        } else if (h[a] < h[b]) {
            t[a] = b;
        } else {
            t[b] = a;
            h[a]++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);

    fin >> N >> M;

    for (int i = 1; i <= M; i++) {
        fin >> v[i].a >> v[i].b >> v[i].c;
    }

    for (int i = 1; i <= N; i++) {
        t[i] = i;
        h[i] = 0;  // Initialize rank as 0
    }

    sort(v + 1, v + M + 1, comp);

    for (int i = 1; i <= M; i++) {
        if (Radacina(v[i].a) != Radacina(v[i].b)) {
            Unire(v[i].a, v[i].b);
            cost += v[i].c;
            cnt++;
            ans.push_back({v[i].a, v[i].b});
            if (cnt == N - 1) break;  // Stop once MST is complete
        }
    }

    fout << cost << "\n";
    fout << cnt << "\n";

    for (auto elem : ans) {
        fout << elem.a << " " << elem.b << "\n";
    }

    return 0;
}