#include <bits/stdc++.h>

using namespace std;

struct Muchie {
    int nod_iesire, cost;
};

vector<Muchie> graf[100005]; // Alocare pentru un număr maxim de noduri
vector<int> tata, d;
int N, M;

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

priority_queue<Muchie, vector<Muchie>, ComparaCost> Q;

void prim() {
    // Initializare
    vector<bool> inAPCM(N + 1, false);
    Q.push({1, 0});  // Începem de la nodul 1 cu cost 0

    while (!Q.empty()) {
        Muchie e = Q.top();
        Q.pop();

        int nod_curent = e.nod_iesire;
        if (inAPCM[nod_curent]) continue;  // Nodul deja inclus în APCM

        // Adăugăm nodul în APCM
        inAPCM[nod_curent] = true;

        // Actualizăm costurile vecinilor neincluși în APCM
        for (const Muchie& vecin : graf[nod_curent]) {
            if (!inAPCM[vecin.nod_iesire] && vecin.cost < d[vecin.nod_iesire]) {
                d[vecin.nod_iesire] = vecin.cost;
                tata[vecin.nod_iesire] = nod_curent;
                Q.push({vecin.nod_iesire, vecin.cost});
            }
        }
    }
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    // Citire date de intrare
    fin >> N >> M;
    tata.resize(N + 1, 0);
    d.resize(N + 1, INT_MAX);

    for (int i = 0; i < M; ++i) {
        int x, y, cost;
        fin >> x >> y >> cost;
        graf[x].push_back({y, cost});
        graf[y].push_back({x, cost});
    }

    // Apelul algoritmului lui Prim
    prim();

    // Afisare rezultate
    int cost_apcm = 0, nr_muchii = 0;
    for (int i = 1; i <= N; ++i) {
        if (d[i] != INT_MAX) {
            cost_apcm += d[i];
            nr_muchii++;
        }
    }

    fout << cost_apcm << "\n";
    fout << nr_muchii << "\n";

    for (int i = 2; i <= N; ++i) {
        fout << tata[i] << " " << i << "\n";
    }

    return 0;
}



/*#include <bits/stdc++.h>

using namespace std;

struct Muchie {
    int nod_iesire, cost;
};

vector<vector<Muchie>> graf;
vector<int> tata, d;
int N, M;

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

priority_queue<Muchie, vector<Muchie>, ComparaCost> Q;

void prim() {
    // Initializare
    vector<bool> inAPCM(N + 1, false);
    Q.push({1, 0});  // Începem de la nodul 1 cu cost 0

    while (!Q.empty()) {
        Muchie e = Q.top();
        Q.pop();

        int nod_curent = e.nod_iesire;
        if (inAPCM[nod_curent]) continue;  // Nodul deja inclus în APCM

        // Adăugăm nodul în APCM
        inAPCM[nod_curent] = true;
        //cout << "Nod adaugat in APCM: " << nod_curent << " cu costul: " << e.cost << "\n";

        // Actualizăm costurile vecinilor neincluși în APCM
        for (const Muchie& vecin : graf[nod_curent]) {
            if (!inAPCM[vecin.nod_iesire] && vecin.cost < d[vecin.nod_iesire]) {
                d[vecin.nod_iesire] = vecin.cost;
                tata[vecin.nod_iesire] = nod_curent;
                Q.push({vecin.nod_iesire, vecin.cost});
            }
        }
    }
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    // Citire date de intrare
    fin >> N >> M;
    graf.resize(N + 1);
    tata.resize(N + 1, 0);
    d.resize(N + 1, INT_MAX);

    for (int i = 0; i < M; ++i) {
        int x, y, cost;
        fin >> x >> y >> cost;
        graf[x].push_back({y, cost});
        graf[y].push_back({x, cost});
    }

    // Apelul algoritmului lui Prim
    prim();

    // Afisare rezultate
    int cost_apcm = 0, nr_muchii = 0;
    for (int i = 1; i <= N; ++i) {
        if (d[i] != INT_MAX) {
            cost_apcm += d[i];
            nr_muchii++;
        }
    }

    fout << cost_apcm << "\n";
    fout << nr_muchii << "\n";

    for (int i = 2; i <= N; ++i) {
        fout << tata[i] << " " << i << "\n";
    }

    return 0;
}
*/