#include <cstdio>
#define NMAX 200005
#define MMAX 400005
///MINHEAP

using namespace std;

struct Muchie{int x,y,c;} G[MMAX];

FILE*fin=fopen("apm.in","r");
FILE*fout=fopen("apm.out","w");

int n,m;
int H[MMAX];
int tata[NMAX];
int h[NMAX];
long long int cost;
int A[NMAX];///retin indicii muchiilor selectate in apm

void creare_heap_combinare(int H[NMAX],int& n);
void combinare(int H[NMAX],int n, int i);
int extragemin(int H[NMAX],int& n);
void citire();
int Find(int x);
void Union(int i,int j);
void afisare();

int main()
{
int i,mmin,cx,cy,nr=0;
citire();
creare_heap_combinare(H,m);
while (nr<n-1)
        {
         mmin=extragemin(H,m);
         cx=Find(G[mmin].x);
         cy=Find(G[mmin].y);
         if (cx!=cy)
            {
             nr++;
             A[nr]=mmin;
             cost+=G[mmin].c;
             Union(cx,cy);
            }
        }
afisare();
    return 0;
}

void afisare()
{
int i;
fprintf(fout,"%d\n",cost);
fprintf(fout,"%d\n",n-1);
for (i=1;i<n;i++)
     fprintf(fout,"%d %d\n",G[ A[i] ].x,G[ A[i] ].y);
}

void creare_heap_combinare(int H[NMAX],int& n)
{
int i;
for (i=1;i<=n;i++) H[i]=i;
for (i=n/2;i>=1;i--) combinare(H,n,i);
}


void combinare(int H[NMAX],int n, int i)
{///se cobina nodul H[i] cu heap-urile cu radacinile 2i si 2i+1, obtinand un nou heap cu radacina H[i]
int x=H[i],tata,fiu;
tata=i; fiu=2*i;
while (fiu<=n) ///exista fiu stang
      {
       if (fiu+1<=n && G[H[fiu+1]].c<G[H[fiu]].c) fiu++;
       ///fiu indica cel mai mic dintre fii
       if (G[H[fiu]].c<G[x].c)
          {
           H[tata]=H[fiu];
           tata=fiu;
           fiu=tata<<1;
           ///fiu=tata*2;
          }
          else ///am gasit locul potrivit pentru x
          break;
      }
H[tata]=x;
}

int extragemin(int H[NMAX],int& n)
{
int minim=H[1];
H[1]=H[n--];
combinare(H,n,1);
return minim;
}

void citire()
{
int i;
//fin>>n>>m;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
    {
     //fin>>G[i].x>>G[i].y>>G[i].c;
     fscanf(fin,"%d %d %d",&G[i].x,&G[i].y,&G[i].c);
    }
}

int Find(int x)
{///caut radacina
int rad=x,aux;
while (tata[rad]) rad=tata[rad];
while (tata[x]) {aux=tata[x]; tata[x]=rad; x=aux;}
return rad;
}

void Union(int i,int j)
{///il fac pe j fiu al lui i
///i si j sunt radacinile arborilor care repr cele doua multimi
if (h[i]<h[j])///i devine fiu al lui j
    tata[i]=j;
    else
    {
     tata[j]=i;
     if (h[i]==h[j]) h[i]++;
    }
}