#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
long i,m,n,componente[200000],conexe,ok,suma,muc;
struct muchii
{
   int x,y;
   int c;
   bool viz;
}s1;
vector <muchii> T;
vector <muchii>::iterator it;
bool compare(muchii aux1, muchii aux2)
{
    return aux1.c<aux2.c;
}
void UF(int min1,int max1)
{
    int i;
    ok=0;
    for(i=1;i<n+1;i++)
    {
        if(componente[i]==max1) { componente[i]=min1; ok=1; }
    }
it->viz=true;
suma=suma+it->c;
muc++;
if(ok==1) conexe--;
}
void krusky()
{
    conexe=n;
    for(it=T.begin();it<T.end();it++)
    {
        if(conexe==1) break;
        if(componente[it->x]!=componente[it->y])  if(componente[it->x]<componente[it->y]) UF(componente[it->x],componente[it->y]);
                                                                          else UF(componente[it->y],componente[it->x]);
    }

}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(i=1;i<m+1;i++)
    {
        fin>>s1.x;
        fin>>s1.y;
        fin>>s1.c;
        T.push_back(s1);
    }
   for(i=1;i<n+1;i++)
      componente[i]=i;
   sort(T.begin(),T.end(),compare);
   krusky();
   fout<<suma<<"\n";
   fout<<muc<<"\n";
   for(it=T.begin();it<T.end();it++)
     if(it->viz==true)  fout<<it->x<<" "<<it->y<<"\n";
   fin.close();
   fout.close();
   return 0;
}