#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int LMAX = 400005;

struct muchie {
    int x, y, c;
};

bool cmp(muchie a, muchie b) {
    return a.c < b.c;
}

muchie L[LMAX];
bool ok;
int father[LMAX/2], n;
vector<int> marb;

int find_root(int x) {
    if (father[x] < 0) {
        return x;
    }
    int root = find_root(father[x]);
    father[x] = root;
    return root;
}

bool unite(int x, int y) {
    int rx, ry;
    rx = find_root(x);
    ry = find_root(y);
    if (rx == ry) return 0;
    //vreau sa leg componenta cu mai putine noduri
    if (rx < ry) swap(rx, ry);
    father[ry] += father[rx];
    if (father[ry] == -n) ok = 1;
    father[rx] = ry;
    return 1;
}


int main()
{
    int m, i, s;
    fin>>n>>m;
    for (i = 0; i < m; i++) {
        int x, y, c;
        fin>>x>>y>>c;
        L[i] = {x, y, c};
    }
    for (i = 1; i <= n; i++) {
        father[i] = -1;
    }
    sort(L, L + m, cmp);
    s = 0;
    ok = 0;
    for (i = 0; i < m && !ok; i++) {
//        cout<<L[i].x<<" "<<L[i].y<<" "<<L[i].c<<"\n";
//        cout<<find_root(L[i].x)<<" "<<find_root(L[i].y)<<"\n";
//        for (int j = 1; j <= n; j++) cout<<father[j]<<" ";
//        cout<<"\n";
        if (unite(L[i].x, L[i].y)) {
            s += L[i].c;
            marb.push_back(i);
        }
    }
    fout<<s<<"\n";
    fout<<marb.size()<<"\n";
    for (i = 0; i < n - 1; i++) {
        fout<<L[marb[i]].x<<" "<<L[marb[i]].y<<"\n";
    }


    fin.close();
    fout.close();
    return 0;
}