#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;

int searchResult(vector<int> arr, int k) {
    auto it = find(arr.begin(), arr.end(), k);
    if (it != arr.end()) {
        return (it - arr.begin());
    } else {
        return -1;
    }
}

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

int extrage_dmin(vector<int>& Q) {
    int dmin = INT_MAX;
    int nod = -1;
    for (int i : Q) {
        if (d[i] < dmin) {
            dmin = d[i];
            nod = i;
        }
    }
    Q.erase(Q.begin() + searchResult(Q, nod));
    return nod;
}

void prim(int s) {
    vector<int> Q(N);
    iota(Q.begin(), Q.end(), 1); // Inițializăm Q cu toate nodurile

    while (!Q.empty()) {
        int u = extrage_dmin(Q);
        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 (searchResult(Q, v) != -1 && muchii[i].cost < d[v]) {
                    d[v] = muchii[i].cost;
                    tata[v] = u;
                }
            }
        }
    }
}

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;
}