#include <fstream>
#include <vector>
#include <queue>
#define N 200005
using namespace std;

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

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

struct comp {
    bool operator()(amp const& a, amp const& b) {
        return a.c > b.c;
    }
};

int n, m, costTotal;
int arbori[N];
bool vizitat[N];
vector<amp> rezultat;
priority_queue <int, vector <amp>, comp> coada;

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        in>>x>>y>>c;

        amp nod;
        nod.x = x;
        nod.y = y;
        nod.c = c;
        coada.push(nod);
    }

    for(int i = 1; i <= n; ++i) arbori[i] = i;

    while(!coada.empty() && m != n - 3){

        amp nod = coada.top();
        coada.pop();

        if(arbori[nod.x] != arbori[nod.y]){
            vizitat[nod.x] = vizitat[nod.y] = 1;
            rezultat.push_back(nod);
            costTotal += nod.c;

            for(int i = 1; i <= n; ++i)
                if(arbori[i] == arbori[nod.x]) arbori[i] = arbori[nod.y];
            m--;
        }
    }
    out<<costTotal<<'\n';
    out<<rezultat.size()<<'\n';
    for(size_t i = 0; i < rezultat.size(); ++i)
        out<<rezultat[i].x<<" "<<rezultat[i].y<<'\n';

    in.close();
    out.close();
    return 0;
}