#include<fstream.h>

#define xn 200001
#define xm 400001

ifstream fin("apm.in");
ofstream fout("apm.out");

int N,M,m[xm][3],t[xn],rang[xn],cost,r[xn][2],nr;

void kruskal();
int multime(int n);
void reuneste(int i,int j);
int poz(int li,int ls);
void quick(int li,int ls);

int main()
{
    int i;
    
    fin>>N>>M;
    
    for(i=0;i<M;i++)
     fin>>m[i][0]>>m[i][1]>>m[i][2];
    
    kruskal();
    
    fout<<cost<<'\n'<<nr<<'\n';
    
    for(i=1;i<=N;i++)
     fout<<r[i][0]<<' '<<r[i][1]<<'\n';
    
    fout.close();
    return 0;
}

int multime(int n)
{
    if(t[n]!=n)
       t[n]=multime(t[n]);
    return t[n];
}

void reuneste(int i,int j)
{
     i=multime(i);
     j=multime(j);
     
     if(i==j) return;
     
     if(rang[i]<rang[j])
        t[i]=j;
     else
        t[j]=i;
     
     if(rang[i]==rang[j])
        rang[i]++;
}

int poz(int li,int ls)
{
    int i=0,j=-1,aux;
    
    while(li<ls)
    {
       if(m[li][2]>m[ls][2])
       {
         aux=-i;         i=-j;         j=aux;
         aux=m[li][0];         m[li][0]=m[ls][0];         m[ls][0]=aux;
         aux=m[li][1];         m[li][1]=m[ls][1];         m[ls][1]=aux;
         aux=m[li][2];         m[li][2]=m[ls][2];         m[ls][2]=aux;
       }
       li+=i;
       ls+=j;
    }
    return li;
}

void quick(int li,int ls)
{
     int k;
     if(li<ls)
     {
       k=poz(li,ls);
       quick(li,k-1);
       quick(k+1,ls);
     }
}

void kruskal()
{
     int i,j,k,c;
     quick(0,M-1);
     
     for(i=1;i<=N;i++)
     {
        t[i]=i;
        rang[i]=0;
     }
     
     for(k=0;k<M;k++)
     {
        i=m[k][0];
        j=m[k][1];
        c=m[k][2];
        
        if(multime(i)==multime(j)) continue;
        
        reuneste(i,j);
        cost+=c;
        r[++nr][0]=j;
        r[nr][1]=i;
     }
}