#include <bits/stdc++.h>

using namespace std;

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

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

void initializare(int s) {
    muchii.resize(N + 1);
    tata.resize(N + 1, 0);
    d.resize(N + 1, INT_MAX);
    d[s] = 0;
}

void prim(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q; // Min-Heap
    Q.push({0, s}); // Adăugăm nodul de start cu costul 0

    while (!Q.empty()) {
        int u = Q.top().second;
        int cost_u = Q.top().first;
        Q.pop();

        if (cost_u > d[u]) {
            continue; // Dacă costul actual este mai mare decât costul din d[], nu actualizăm
        }

        for (int i = 0; i < M; i++) {
            if (muchii[i].nod_intrare == u || muchii[i].nod_iesire == u) {
                int v = (muchii[i].nod_intrare == u) ? muchii[i].nod_iesire : muchii[i].nod_intrare;
                if (muchii[i].cost < d[v]) {
                    d[v] = muchii[i].cost;
                    tata[v] = u;
                    Q.push({d[v], v}); // Adăugăm nodul în min-heap cu noul 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
    initializare(s);
    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;
}