#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;
int N, M;

void prim(int s, int& cost_apcm) {
    priority_queue<muchie, vector<muchie>, ComparaCost> Q;
    vector<bool> vizitat(N + 1, false);

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

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

        int u = min_muchie.nod_iesire;
        if (vizitat[u]) {
            continue;
        }

        vizitat[u] = true;
        tata[u] = min_muchie.nod_intrare;
        cost_apcm += min_muchie.cost;

        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 (!vizitat[v]) {
                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);

    int cost_apcm = 0;
    prim(s, cost_apcm);

    // Afișarea costului total al arborelui de acoperire minim
    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) {
        fout << tata[u] << " " << u << endl;
    }

    return 0;
}