#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct muchie{
              int x;
              int y;
              int c;
              }a[170000];
int t[170000];
int compare(const void *a,const void *b)
{
    return ((*(muchie*)a).c-(*(muchie*)b).c);
}
/*void sort(muchie b[100000],int n)
{
     int c=0,i;
     muchie f;
     while(!c)
     {
              c=1;
              for(i=1;i<n;i++)
              if(b[i].c>b[i+1].c){
                                  f=b[i];
                                  b[i]=b[i+1];
                                  b[i+1]=f;
                                  c=0;
                                  }
     }
} */
int findset(int u)
{
    if(t[u]==0)return u;
    else return t[u]=findset(t[u]);
}
void uniune(int u,int v,int h[170000])
{
     //u=findset(u,t);
     //v=findset(v,t);
     if(h[u]>h[v])t[v]=u;
     else {
           t[u]=v;
           if(h[u]==h[v])h[v]++;
           }
}
                             
int main()
{
    //ifstream f("apm.in");
    //ofstream g("apm.out");
    FILE *f=fopen("apm.in","r");
    FILE *g=fopen("apm.out","w");
    
    int n,m,i,j,k,s=0,nr=0,h[170000],cost,u,v;
    muchie b[60000];
    fscanf(f,"%d%d",&n,&m);
    //f>>n>>m;
    for(k=0;k<m;k++)
    {
                     //f>>i>>j>>cost;
                     fscanf(f,"%d%d%d",&a[k].x,&a[k].y,&a[k].c);
                     /*a[k].x=i;
                     a[k].y=j;
                     a[k].c=cost;*/
    }
    for(i=1;i<=n;i++)
    {
    t[i]=0;
    h[i]=0;
    }
    
    
    qsort(a,m,sizeof(muchie),compare);
    
    for(k=0;k<m &&nr<=n-1;k++)
    {
     u=findset(a[k].x);
     v=findset(a[k].y);
     if(u!=v){
                                         s+=a[k].c;
                                         nr++;
                                         b[nr].x=a[k].x;
                                         b[nr].y=a[k].y;
                                         uniune(u,v,h);
                                         }
     }
                                         
                                         
    

   
    //g<<s<<endl;
    fprintf(g,"%d\n",s);
    fprintf(g,"%d\n",nr);
    //g<<nr<<endl;
    for(i=1;i<=nr;i++)
    //g<<b[i].x<<" "<<b[i].y<<endl;
    fprintf(g,"%d %d\n",b[i].x,b[i].y);

//system("pause");
return 0;
}