#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {
    int x,y,c;
} M[500010],aux, ans[500010];
int T[500010],H[500010],n,m,k,nr_muchii;

void citire()
{
    k = 1;
    fin>>n>>m;
    while(fin>>M[k].x>>M[k].y>>M[k].c) k++;
}
bool comp ( muchie a, muchie b)
{
    if(a.c<b.c)
        return 1;
    return 0;
}
int arb(int z)
{
    while(T[z])
        z=T[z];
    return z;
}
int main()
{
    int i,sum,a, b, stop;
    sum=0;
    citire();
    sort(M+1,M+m+1,comp);
    k=1;
    do{
        stop=0;
        while(stop==0)
        {
            a=arb(M[k].x);
            b=arb(M[k].y);
            if(a == b)
                k++;
            else stop=1;
        }
        nr_muchii++;
        ans[nr_muchii]=M[k];
        sum+=M[k].c;
        if( H[a] == H[b] )
        {
            if(T[M[k].x] == 0)
            {
                T[M[k].x] = M[k].y;
                H[M[k].y]++;
            }
           else {
                    if(T[M[k].y] == 0)
                    {
                        T[M[k].y] = M[k].x;
                        H[M[k].x]++;
                    }
                   else
                    {
                        T[a] = b;
                        H[b]++;
                    }
                 }
        }
        else
        {
            if( H[a] < H[b] )
               T[a] = b;
            else
               T[b] = a;
        }
        k++;
       }while(nr_muchii<n-1);

       fout<<sum<<'\n'<<nr_muchii<<'\n';
       for(i=1;i<=nr_muchii;i++)
       {
           fout << ans[i].x << " " << ans[i].y <<'\n';
       }
    fin.close();
    fout.close();
    return 0;
}