#include<iostream>
#include<fstream>
#include <algorithm>

using namespace std;

int a[100][100],n,i,infinit=1000000,s[100];
int x,y,m,j,cost,start,t[100],nrc=0,k=0;

typedef struct o_muchie
{
        int x,y,cost;
        }
        TIPUL_MUCHIE;
        
TIPUL_MUCHIE v[100],muchiile_apm[100];

void citire()
{ 
	ifstream f("apm.in");
        f>>n>>m;
     
     for(i=1;i<=m;i++)
         f>>v[i].x>>v[i].y>>v[i].cost;
               

 f.close();
 
 }

void ordoneaza_muchiile()
{
  
  int ordonat;
  
  TIPUL_MUCHIE aux;
  
  do{
      ordonat=1;
        for(i=1;i<m;i++)
           if (v[i].cost>v[i+1].cost)
              {
              aux=v[i];
              v[i]=v[i+1];
              v[i+1]=aux;
              ordonat=0;
              }
              }
           while(ordonat==0);
  
}

void apm_kruskal()
{
     int o_adaugam,xx,yy,nr_componentei_lui_xx=0;
    
    for(i=1;i<=m;i++)
      
      {
      o_adaugam=1;
                  
      xx=v[i].x;
      yy=v[i].y;
    
	if (t[xx]==0&&t[yy]==0) 
	{
		nrc++;
        t[xx]=t[yy]=nrc;
	}
                                       
    else
      if (t[xx]!=0&&t[yy]==0) t[yy]=t[xx];
            else
              if (t[xx]==0&&t[yy]!=0) t[xx]=t[yy];
              else
           if (t[xx]!=t[yy])
               {
                  nr_componentei_lui_xx=t[xx];
				  
                  for(j=1;j<=n;j++)
                    if (t[j]==nr_componentei_lui_xx)
                      t[j]=t[yy];
				}
			else 
	          o_adaugam=0;
                      
       if (o_adaugam==1)
          {            k++;
                       muchiile_apm[k].x=v[i].x;
                       muchiile_apm[k].y=v[i].y;
                       muchiile_apm[k].cost=v[i].cost;
                       }
       }                        
}         

void afisare()
{int s=0;

     for(i=1;i<=k;i++)
       {
		s=s+muchiile_apm[i].cost;
		}
	
ofstream g("apm.out");	 
    g<<s;
    g<<"\n"<<k<<"\n";

 for(i=1;i<=k;i++)
  g<<muchiile_apm[i].y<<" "<<muchiile_apm[i].x<<"\n";	
       }  

int main()
{
    citire();
    
    ordoneaza_muchiile();

    apm_kruskal();
    
    afisare();
  
    return 0;
}