#include<iostream>
#include<fstream>
#include <algorithm>
using namespace std;
int n,i,infinit=1000000,x,y,m,j,cost,start,t[100],nrc=0,k=0,s=0;

typedef struct o_muchie
{
        int x,y,cost;
        }
        TIPUL_MUCHIE;
        
TIPUL_MUCHIE v[10000],muchiile_apm[10000];
//*******************CITIREA DATELOR
//*******************GRAFUL ESTE ORIENTAT

void citire()
{ ifstream f("apm.in");
f>>n>>m;// N NODURI SI M MUCHII 
           //URMEAZA M LINII CU CATE TREI VALORI PE FIECARE LINIE
           //   1 2 4       INSEAMNA ARC DE LA 1 LA 2 DE COST 4

     
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;// adaugam muchia doar daca nu face parte din aceasi componenta
                  // altfel s-ar forma un ciclu si rezultatul nu ar mai fi un arbore
                  
      xx=v[i].x;// am folosit xx si yy pentru a nu fi nevit sa scriu de fiecare data v[i].x si v[i].y
      yy=v[i].y;
    
    // despre vectorul t:
    //  t[i]=0 daca nu a fost selectat nodul i
    // t[i]=nrc  inseamna ca face parte din componeneta nrc(nrc=1,2,  ...)
         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;
                       s=s|+v[i].cost;
                       }
       }                        
}         


void afisare()
{
     ofstream g("apm.out");
     g<<s<<endl<<n-1<<endl;
     cout<<endl;
     for(i=1;i<=k;i++)
     
                      g<<muchiile_apm[i].x<<" "<<muchiile_apm[i].y<<endl;
       g.close();           
         
       }    
int main()
{
    citire();//am pus in ahiva si fisierul de intrare 
             // este acelasi fisier cu cel de pe infoarena
    
    ordoneaza_muchiile();
    
    
    apm_kruskal();
    
    afisare();
    
    return 0;
}