#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define DN 200001
#define DM 400001

using namespace std;

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

int n, m, gr[DN], ind[DM], x[DM], y[DM], c[DM], t;
vector < pair < int, int > > rasp;

bool cmp(int i, int j)
{
    return(c[i]<c[j]);
}
int grupa(int i)
{
    if(gr[i]==i)
        return i;
    gr[i]=grupa(gr[i]);
    return gr[i];
}
void reuniune(int x, int y)
{
    gr[grupa(x)]=grupa(y);
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
        gr[i]=i;
    for(int i=1; i<=m; i++)
    {
        fin>>x[i]>>y[i]>>c[i];
        ind[i]=i;
    }
    sort(ind+1, ind+m+1, cmp);
    for(int i=1; i<=m; i++)
    {
        if(grupa(x[ind[i]])!=grupa(y[ind[i]])){
            reuniune(x[ind[i]],y[ind[i]]);
            rasp.push_back(make_pair(x[ind[i]],y[ind[i]]));
            t+=c[ind[i]];
        }
    }
    fout<<t<<"\n"<<rasp.size()<<"\n";
    for(int i=0; i<rasp.size(); i++)
        fout<<rasp[i].first<<" "<<rasp[i].second<<"\n";
    fin.close();
    fout.close();
    return 0;
}