#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

#define NMAX 200005

int n, m, sol;
bool viz[NMAX];
vector<pair<int, int>> G[NMAX];
vector<pair<int, int>> sol_muchii;
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<>> q;

void citire() {
    f >> n >> m;
    int x, y, c;
    for (int i = 0; i < m; ++i) {
        f >> x >> y >> c;
        G[x].push_back({c, y});
        G[y].push_back({c, x});
    }
}

void adaugare_vecini_in_queue(int nod) {
    viz[nod] = true;
    for (auto &nod2: G[nod])
        if (!viz[nod2.second]) {
            pair<int, pair<int, int>> val = {nod2.first, {nod2.second, nod}};
            q.push(val);
        }
}

void prelucrare() {
    adaugare_vecini_in_queue(1);
    while (!q.empty()) {
        pair<int, pair<int, int>> nod = q.top();
        q.pop();
        if (viz[nod.second.first])
            continue;
        adaugare_vecini_in_queue(nod.second.first);
        sol += nod.first;
        sol_muchii.push_back(nod.second);
    }
}

void afisare() {
    g << sol << '\n' << sol_muchii.size();
    for (auto &muchie: sol_muchii) {
        g << '\n' << muchie.first << ' ' << muchie.second;
    }
}

int main() {
    citire();
    prelucrare();
    afisare();
    return 0;
}