#include <fstream>
#include <algorithm>
using namespace std;
struct muchie {int x,y,c;};
muchie M[400010],aux, ans[400010];
int T[400010],H[400010],n,m,k,nr_muchii;
ifstream fin("apm.in");
ofstream fout("apm.out");
void citire()
{
    k = 1;
    fin>>n>>m;
    while(fin>>M[k].x>>M[k].y>>M[k].c) k++;
    fin.close();
}
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';
       }
    return 0;
}