#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct muchie{
              int x;
              int y;
              int c;
              }a[170000];
int t[170000],h[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,int t[170000])
{
    if(t[u]==0)return u;
    else return findset(t[u],t);
}
void uniune(int u,int v,int t[170000],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");
    int n,m,i,j,k,/*t[170000],*/s=0,nr=0,/*h[170000],*/cost,u,v;
    muchie b[60000];
    f>>n>>m;
    for(k=0;k<m;k++)
    {
                     f>>i>>j>>cost;
                     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,t);
     v=findset(a[k].y,t);
     if(u!=v){
                                         s+=a[k].c;
                                         nr++;
                                         b[nr].x=a[k].x;
                                         b[nr].y=a[k].y;
                                         uniune(u,v,t,h);
                                         }
     }
                                         
                                         
    

   
    g<<s<<endl;
    g<<nr<<endl;
    for(i=1;i<=nr;i++)
    g<<b[i].x<<" "<<b[i].y<<endl;

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