#include<iostream>
#include<fstream>
using namespace std;
struct muchie{
              int x;
              int y;
              int c;
              }a[10000];
void sort(muchie b[100],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 main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,m,i,j,k,color[10000],t,s=0,nr=0;
    muchie b[40000];
    f>>n>>m;
    for(k=1;k<=m;k++)
    {
                     f>>i>>j>>t;
                     a[k].x=i;
                     a[k].y=j;
                     a[k].c=t;
    }
    for(i=1;i<=n;i++)
    color[i]=i;
    /*for(i=1;i<=m;i++)
    cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].c<<endl;*/
    sort(a,m);
    /*cout<<"muchiile sunt: "<<endl;
    for(i=1;i<=m;i++)
    cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].c<<endl;*/
    for(k=1;k<=m;k++)
    {
                     if(color[a[k].x]!=color[a[k].y]){
                                                     s+=a[k].c;
                                                     nr++;
                                                     b[nr].x=a[k].x;
                                                     b[nr].y=a[k].y;
                                                     //b[a[k].x][a[k].y]=b[a[k].y][a[k].x]=a[k].c;
                                                     
                                                     for(i=1;i<=n;i++)
                                                     {
                                                      if(color[i]==color[a[k].x] && i!=a[k].x)color[i]=color[a[k].y];
                                                      }
                                                      color[a[k].x]=color[a[k].y];
                                                      }
    }
    g<<s<<endl;
    g<<nr<<endl;
    for(i=1;i<=nr;i++)
    g<<b[i].x<<" "<<b[i].y<<endl;
//cout<<"Arborele partial este "<<endl;
/*for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
if(b[i][j])g<<i<<" "<<j<<endl;*/
//cout<<b[i][j]<<" ";
//cout<<endl;
//system("pause");
return 0;
}