#include <fstream>
#define MaxN 200001
#define MaxM 400001
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m, tata[MaxN],k, A[MaxM], B[MaxM];
int cost;
struct lista
{
    int a,b,cost;
    lista *urm;
};
lista *first, *nou, *tmp, *last, *tm;
int tatuca(int x)
{
    if(tata[x]!=x) tata[x]=tatuca(tata[x]);
    return tata[x];
}
void apm()
{
    int i, ta, tb;
    for(i=1;i<=n;i++)
        tata[i]=i;
    tmp=first;
    while(k<n-1)
    {
        ta=tatuca(tmp->a);
        tb=tatuca(tmp->b);
        if(ta!=tb)
        {
            cost=cost+tmp->cost;
            k++;
            A[k]=tmp->a;
            B[k]=tmp->b;
            tata[ta]=tb;
        }
        tmp=tmp->urm;
    }
}
int main()
{
    int a,b,c,i,j;
    last=new lista;
    last->cost=2000000000;
    last->urm=0;
    in>>n>>m;
    in>>a>>b>>c;
    first = new lista;
    first->a=a; first->b=b; first->cost=c;
    first->urm=last;
    for(i=2;i<=m;i++)
    {
        in>>a>>b>>c;
        nou=new lista;
        nou->a=a; nou->b=b; nou->cost=c;
        if(c <= first->cost)
        {
            nou->urm=first;
            first=nou;
        }
        else
        {
            tmp=first;
            tm=first->urm;
            while( (tm->cost)<(c))
            {
                tmp=tmp->urm;
                tm=tm->urm;
            }
            nou->urm=tm;
            tmp->urm=nou;
        }
    }
    apm();
    out<<cost<<"\n";
    out<<n-1<<"\n";
    for(i=1;i<=k;i++)
        out<<B[i]<<" "<<A[i]<<"\n";
    out.close();
    in.close();
    return 0;
}