#include <fstream>
#include <vector>

using namespace std;

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

struct muchie
{
    int a,b,cost;
};

muchie v[251];

int t[200001],x,y;

int tata(int x)
{
    if(t[x]==x)
        return x;
    return t[x]=tata(t[x]);
}

void join(int x, int y)
{
    int rx,ry;
    rx=tata(x);
    ry=tata(y);
    t[rx]=ry;
}

bool cmp (muchie x, muchie y)
{
    if(x.cost<y.cost)
        return true;
    else return false;
}

void sort(muchie x, muchie y)
{

    if(x.cost>y.cost)
        cmp(x,y);

}

int main()
{
    int n,m,mm,s=0;

    f>>n>>m;

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

    for(int i=1;i<=m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].cost;
        f>>v[i+1].a>>v[i+1].b>>v[i+1].cost;
        i++;
        sort(v[i],v[i+1]);
    }

    mm=n-1;

    for(int i=1;i<=mm;i++)
        s=s+v[i].cost;

    g<<s<<endl;
    g<<mm<<endl;

    for(int i=1;i<mm;i++)
        g<<v[i].a<<" "<<v[i].b<<endl;

    f.close();
    g.close();

    return 0;
}