#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie {
    int y, c;
};
set<tuple<int, int, int>> s;

vector<Muchie> gr[200002];
vector<Muchie> rasp;

int n, m, i, ram, costTot;
bool viz[200002];

int main() {
    //ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        gr[x].push_back(Muchie{y, c});
        gr[y].push_back(Muchie{x, c});
    }

    ram = n - 1;
    viz[1] = true;
    for(Muchie urm : gr[1]) {
        s.insert(make_tuple(urm.c, urm.y, 1));
    }

    while(ram) {
        int nod, cost, ant;
        tie(cost, nod, ant) = *s.begin();
        s.erase(s.begin());

        if(!viz[nod]) {
            costTot += cost;
            viz[nod] = true;
            ram--;

            rasp.push_back({ant, nod});

            for(Muchie urm : gr[nod]) {
                if(!viz[urm.y]) s.insert(make_tuple(urm.c, urm.y, nod));
            }
        }
    }
    fout << costTot << "\n" << rasp.size() << "\n";
    for(Muchie cur : rasp) fout << cur.y << " " << cur.c << "\n";

    return 0;
}