#include <fstream>
#define NMAX 200002
#define MMAX 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,nr,m,cx,cy;
int h[MMAX];
int tata[MMAX];
int Find(int x);
void Union (int x,int y);

struct muchie{
            int x,y,cost;
            friend bool operator < (muchie a,muchie b);
            friend bool operator <= (muchie a,muchie b);
            friend bool operator >= (muchie a,muchie b);
            friend bool operator > (muchie a,muchie b);

                };
muchie H[MMAX],a[NMAX];
bool operator < (muchie a,muchie b)
{
    return a.cost<b.cost;
}
bool operator <= (muchie a,muchie b)
{
    return a.cost<=b.cost;
}
bool operator >= (muchie a,muchie b)
{
    return a.cost>=b.cost;
}
bool operator > (muchie a,muchie b)
{
    return a.cost>b.cost;
}
int nrsel,costtotal;muchie mmin;
void creare();
void afisare(int n, muchie H[]);
void inserare(int &n,muchie H[], muchie x);
void combinare(int n,muchie H[],int poz);   ///poz=pozitia radacinii
muchie  extragemin(int &n , muchie H[]);
void heapsort();
int main()
{//citire(n,H);
    int i,j;
    creare();
    while(nrsel<n-1)
    {
        mmin=extragemin(m,H);
        cx=Find(mmin.x);
        cy=Find(mmin.y);
        if(cx!=cy)
        {
            nrsel++;
            costtotal+=mmin.cost;
            a[nrsel]=mmin;
            Union(cx,cy);
        }

    }
    fout<<costtotal<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        fout<<a[i].x<<' '<<a[i].y<<'\n';
    return 0;
}

void afisare(int n, int H[] )
{
int i;
for(i=1;i<=n;i++)
     fout<<H[i]<< " ";
fout.close();
}
void inserare(int &n,int H[], int x)
{int fiu, tata;
 fiu=++n; tata=fiu/2;
 ///fiu= pozitia pe care vreau sa il pun pe x
 while(tata && H[tata]>x)
    {
     H[fiu]=H[tata];
     fiu=tata;
     tata=fiu/2;
    }
 H[fiu]=x;
}
void combinare(int n,muchie H[],int poz)
{int fiu,tata;
 muchie x=H[poz];
 tata=poz;fiu=2*tata;  ///fiul stang
 while(fiu<=n)
    {
     if(fiu+1<=n && H[fiu+1]<H[fiu]) fiu++;
     ///fiul e min deci daca il pun in locul tatalui se respecta ordinea
     if(x <= H[fiu]) break; ///daca emai mic decat minim e aranjat, nu fac nik
     H[tata]=H[fiu];
     tata=fiu;
     fiu=2*tata;
    }
 H[tata]=x;

}

void creare()
{int i;
  fin>>n>>m;
  for(i=1;i<=m;i++)  fin>>H[i].x>>H[i].y>>H[i].cost;
  for(i=m/2;i>0;i--)  ///fiecare element de la care poate porni un graf(trebuie sa aiba fiu)
        combinare(m,H,i);
}
muchie extragemin(int &n , muchie H[])
{muchie minim;
minim=H[1];///iau elementul si resortez (ala era cel mai mic)
H[1]=H[n--];
combinare(n,H,1);
return minim;
}
int Find(int x)
{
    int rad=x;int aux;
    while(tata[rad])
        rad=tata[rad];
    while(tata[x])
    {   aux=tata[x];
        tata[x]=rad;
        x=aux;
    }
    return rad;
}
void Union(int x,int y)
{   if(h[x]<h[y])
    tata[x]=y;
    else
    {tata[y]=x;if(h[x]==h[y])h[x]++;}
}