#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
struct bound
{
    long x, y, c;
};
bool cmp(const bound &x, const bound &y)
{
    return x.c<y.c;
}
long n, m, sum;
long *group;
bound *bounds;
vector<long> selected;
bool sameGroup(long x, long y)
{
    long r1, r2, aux;
    r1=x;
    while(group[r1]) r1=group[r1];
    while(group[x])
    {
        aux=group[x];
        group[x]=r1;
        x=aux;
    }
    r2=y;
    while(group[r2]) r2=group[r2];
    while(group[y])
    {
        aux=group[y];
        group[y]=r2;
        y=aux;
    }
    if(r1!=r2)
    {
        group[r1]=r2;
        return false;
    }
    else return true;
}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in>>n>>m;
    group = new long[n+1];
    bounds = new bound[m];
    for(long i=1; i<=n; ++i) group[i]=0;
    for(long i=0; i<m; ++i)
        in>>bounds[i].x>>bounds[i].y>>bounds[i].c;
    sort(bounds, bounds+m, cmp);
    for(long i=0; i<m; ++i)
    {
        if(!sameGroup(bounds[i].x, bounds[i].y))
        {
            sum+=bounds[i].c;
            selected.push_back(i);
        }
    }
    out<<sum<<'\n';
    out<<selected.size()<<'\n';
    for(vector<long>::iterator it=selected.begin(), ed=selected.end(); it!=ed; ++it)
        out<<bounds[*it].x<<' '<<bounds[*it].y<<'\n';
    return 0;
}