#include<fstream>
using namespace std;
long ki[400001],ii[400001];
struct mm{
    long x,y;
    int c;
}t[400001];
void q(long e,long v)
{
    if(e<v)
    {
        long k;
        k=t[(e+v)/2].c;
        long i,j;
        i=e-1;
        j=v+1;
        while(i<j)
        {
            do{
                i++;
            }while(t[i].c<k);
            do{
                j--;
            }while(t[j].c>k);
            if(i<j)
                swap(t[i],t[j]);
        }
        q(e,j);
        q(j+1,v);
    }
}
long r(long i)
{
    if(ii[i]==i)
        return i;
    ii[i]=r(ii[i]);
    return ii[i];
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    long i,n,m;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>t[i].x>>t[i].y>>t[i].c;
    q(1,m);
    for(i=1;i<=n;i++)
        ii[i]=i;
    long h=0,o=0;
    i=1;
    while(h<n-1)
    {
        if(r(t[i].x)!=r(t[i].y))
        {
            ki[++h]=i;
            o+=t[i].c;
            ii[r(t[i].x)]=r(t[i].y);
        }
        i++;
    }
    g<<o<<"\n"<<n-1<<"\n";
    for(i=1;i<n;i++)
        g<<t[ki[i]].x<<" "<<t[ki[i]].y<<"\n";
    f.close();
    g.close();
    return 0;
}