#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,nr,ind1,ind2,nh;
int h[200008];
int c[200008],c1,c2;
int costmin;

struct muchie{int x,y; int c;
            };
muchie G[400008], sol[400008];

void citire();
int Find(int x);
void Union(int i, int j);
void kruskal();
void combinare(int rad, int n);
muchie extrage(int &n);
void afisare();

int main()
{
    int i;
    citire();
    for(i=m/2;i>0;i--)
        combinare(i,m);
    kruskal();
    afisare();
    fout.close();
    return 0;
}

void citire()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
          fin>>G[i].x>>G[i].y>>G[i].c;

}

muchie extrage(int &n)
{
    muchie x=G[1];
    //ind1=G[1].x,ind2=G[1].y;
    G[1]=G[n]; n--;
    combinare(1, n);
    return x;
}

void kruskal()
{
    int i,j;
    muchie cost;
    //for(i=1;i<=m;i++) c[i]=i;
    for(i=1;i<=n-1;i++)
        {
            cost=extrage(m);
            c1=Find(cost.x); c2=Find(cost.y);
            if(c1!=c2)
            {
                //fout<<G[ind1].x<<' '<<G[ind2].y<<'\n';
                sol[++nr].x=cost.x; sol[nr].y=cost.y;
                costmin+=cost.c;
                Union(c1,c2);
            }
            else i--;
        }
    //fout<<costmin<<'\n';
    //fout<<nr;
}

int Find(int x)
{
    int rad=x,vf;
    while(c[rad]!=0) rad=c[rad];

     while(c[x]!=0)
     {
         vf=x; x=c[x]; c[vf]=rad;
     }
     return rad;
}

void Union(int i, int j)
{
    if(h[i]<h[j]) c[i]=j;
    else
        if(h[i]>h[j]) c[j]=i;
        else
            if(h[i]==h[j]) {c[j]=i; h[i]++;}
}

void combinare(int rad,int n)
{
     int fiu,tata,x;
     muchie aux;
     //st=G[rad].x; dr=G[rad].y;
     x=G[rad].c; aux=G[rad];
     tata=rad; fiu=2*rad;
     while(fiu<=n)
     {
        if(fiu+1<=n&&G[fiu].c>G[fiu+1].c) fiu++;
        if(x>G[fiu].c)
        {
          G[tata]=G[fiu];
          tata=fiu; fiu=2*tata;
        }
        else break;
     }
     //G[tata].c=aux; G[tata].x=st;  G[tata].y=dr;
      G[tata]=aux;
}

void afisare()
{
    int i;
    fout<<costmin<<'\n';
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
        fout<<sol[i].x<<' '<<sol[i].y<<'\n';
}