#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, muchii[2][200001], viz[200001], l;
struct muchie
{
    int x,y,cost;
}v[400000];
bool mod(muchie a, muchie b)
{
    return a.cost < b.cost;
}
void prim()
{
    int i, k = 1, apm;
    sort(v + 1, v + m + 1, mod);
    while (v[k].x != 1 && v[k].y != 1) {k++;}
    viz[v[k].x] = 1;
    viz[v[k].y] = 1;
    muchii[0][++l] = v[k].y;
    muchii[1][l] = v[k].x;
    apm = v[k].cost;
    for (i = 3; i <= n; i++) {
        k = 1;
        while (viz[v[k].x] == viz[v[k].y])
            k++;
        if (viz[v[k].x] == 1)
            viz[v[k].y] = 1;
        else
            viz[v[k].x] = 1;
        apm += v[k].cost;
        muchii[0][++l] = v[k].y;
        muchii[1][l] = v[k].x;
    }
    fout << apm;
}
int main()
{
    int i;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;
    prim();
    fout << "\n" << l << "\n";
    for (i = 1; i <= l; i++)
        fout << muchii[0][i] << " " << muchii[1][i] << "\n";
    fin.close();
    fout.close();
    return 0;
}