#include <iostream>
#include <fstream>
using namespace std;

long l[400001],nrm,ct,n,m;

struct muchie {
    long x,y,c;
}v[400001],aux,t[400001];

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

void quickSort(long left, long right)
{
      long i = left, j = right;
      long pivot = v[(left + right) / 2].c;

      /* partition */
      while (i <= j)
      {
            while (v[i].c < pivot)
                  i++;
            while (v[j].c > pivot)
                  j--;
            if (i <= j)
            {
              aux = v[i];
              v[i] = v[j];
              v[j] = aux;
              i++;
              j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(left, j);
      if (i < right)
            quickSort(i, right);
}

void ordo ()
{
    long i,j;
    for (i=1;i<m;i++)
        for (j=i+1;j<=m;j++)
            if (v[i].c>v[j].c)
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }
}
void apm_kruskal()
{
    long i,k,nr1,nr2,j;
    quickSort(1,m);
    for (j=1;j<=n;j++)
        l[j]=j;
    ct=0;k=0;i=1;
    while (i<=m)
    {
        if (l[v[i].x]!=l[v[i].y])
        {

            nrm++;
            t[nrm].x=v[i].x;
            t[nrm].y=v[i].y;
            //cout<<"("<<v[i].x<<","<<v[i].y<<")"<<" ";
            ct+=v[i].c;
            nr1=l[v[i].x];
            nr2=l[v[i].y];
            k=nr1;
            for (j=1;j<=n;j++)
                if (l[j]==nr2)
                    l[j]=nr1;
        }
        i++;
    }
    ofstream g ("apm.out");
    g<<ct<<endl;
    g<<nrm<<endl;
    for (int i=1;i<=nrm;i++)
        g<<t[i].x<<" "<<t[i].y<<endl;
        g.close();
}

int main ()
{
    citire();
    apm_kruskal();
    return 0;
}