#include <bits/stdc++.h>

using namespace std;

struct muchie {
    int nod_intrare, nod_iesire, cost;
};

struct ComparaCost {
    bool operator()(const muchie& a, const muchie& b) const {
        return a.cost > b.cost; // Min-heap, sortare după cost descrescător
    }
};

vector<muchie> muchii;
vector<int> tata, d;
int N, M;

void prim(int s) {
    priority_queue<muchie, vector<muchie>, ComparaCost> Q;

    Q.push({s, s, 0});

    while (!Q.empty()) {
        muchie min_muchie = Q.top();
        Q.pop();

        int u = min_muchie.nod_iesire;

        if (tata[u] != 0) {
            continue; // Nodul deja inclus în arbore
        }

        tata[u] = min_muchie.nod_intrare;

        for (int i = 0; i < M; i++) {
            int v;
            if (muchii[i].nod_intrare == u) {
                v = muchii[i].nod_iesire;
            } else if (muchii[i].nod_iesire == u) {
                v = muchii[i].nod_intrare;
            } else {
                continue;
            }

            if (tata[v] == 0 && muchii[i].cost < d[v]) {
                d[v] = muchii[i].cost;
                Q.push({u, v, muchii[i].cost});
            }
        }
    }
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int u, v, c;
        fin >> u >> v >> c;
        muchie m;
        m.nod_intrare = u;
        m.nod_iesire = v;
        m.cost = c;
        muchii.push_back(m);
    }

    int s = 1; // Nodul de start
    tata.resize(N + 1, 0);
    d.resize(N + 1, INT_MAX);
    d[s] = 0;

    prim(s);

    // Calcularea și afișarea costului total al arborelui de acoperire minim
    int cost_apcm = accumulate(d.begin() + 2, d.end(), 0); // Excludem costul nodului de start
    fout << cost_apcm << endl;

    // Afișarea numărului de muchii ale arborelui de acoperire minim
    int numar_muchii_apcm = count_if(tata.begin() + 2, tata.end(), [](int parent) { return parent != 0; });
    fout << numar_muchii_apcm << endl;

    // Afișarea muchiilor arborelui de acoperire
    for (int u = 2; u <= N; ++u) { // Începem de la 2 pentru a evita nodul de start
        if (tata[u] != 0) {
            fout << tata[u] << " " << u << endl;
        }
    }

    return 0;
}