#include <fstream>
#include <cstdlib>
#define nMax 200001
#define mMax 400001

using namespace std;

 ifstream x ("apm.in");
 ofstream y ("apm.out");

 struct struct1
 {
     int u;
     int v;
     int weight;
 };

 struct stack
 {
     int u;
     int v;
     stack *next;
 };

 int n,m;
 int joint,number,sum;
 int disjoint[nMax];
 struct1 edge[mMax];
 stack *head;
 stack *tail;

 void quicksort(int l, int r)
 {
     int i,j;
     int pivot,p;

     struct1 aux;

     p=rand()%(r-l+1)+l;

     pivot=edge[p].weight;

     aux=edge[p];
     edge[p]=edge[l];
     edge[l]=aux;

     i=l+1;

     for(j=l+1;j<=r;j++)
        if(pivot>edge[j].weight)
        {
            aux=edge[i];
            edge[i]=edge[j];
            edge[j]=aux;

            i++;
        }

     aux=edge[i-1];
     edge[i-1]=edge[l];
     edge[l]=aux;

     if(l<i-2)
        quicksort(l,i-2);
     if(i<r)
        quicksort(i,r);
 }

 void add(int u, int v)
 {
     stack *temp;

     if(!head)
     {
         head=new stack();

         head->u=u;
         head->v=v;
         head->next=NULL;
         tail=head;
     }
     else
     {
         temp=new stack();

         temp->u=u;
         temp->v=v;
         temp->next=NULL;
         tail->next=temp;
         tail=temp;
     }
 }

 void combine(int u, int v, int j)
 {
     int i,k;

     if(disjoint[u]!=disjoint[v] && disjoint[u] && disjoint[v])
     {
         k=disjoint[v];

         for(i=1;i<=n;i++)
            if(disjoint[i]==k)
               disjoint[i]=disjoint[u];

         number++;
         sum+=j;
         add(u,v);
     }
     else
        if(disjoint[u]==disjoint[v] && disjoint[u]==0)
        {
            joint++;

            disjoint[u]=disjoint[v]=joint;

            number++;
            sum+=j;
            add(u,v);
        }
        else
           if(disjoint[u]!=disjoint[v] && (disjoint[u]==0 || disjoint[v]==0))
              if(disjoint[u]==0)
              {
                  disjoint[u]=disjoint[v];

                  number++;
                  sum+=j;
                  add(u,v);
              }
              else
                 if(disjoint[v]==0)
                 {
                     disjoint[v]=disjoint[u];

                     number++;
                     sum+=j;
                     add(u,v);
                 }
/*
     for(i=1;i<=n;i++)
       y<<disjoint[i]<<' ';
     y<<'\n';
*/
 }

int main()
{
    int i;

    x>>n>>m;

    for(i=1;i<=m;i++)
    {
        x>>edge[i].u;
        x>>edge[i].v;
        x>>edge[i].weight;
    }

    quicksort(1,m);
/*
    for(i=1;i<=n;i++)
       y<<edge[i].u<<" <--> "<<edge[i].v<<" ("<<edge[i].weight<<") "<<"\n";
    y<<'\n';
*/
    for(i=1;i<=m;i++)
       combine(edge[i].u,edge[i].v,edge[i].weight);
/*
    for(i=1;i<=n;i++)
       y<<disjoint[i]<<' ';
    y<<'\n';
*/
    y<<sum<<'\n';
    y<<number<<'\n';

    stack *temp;

    temp=head;
    while(temp)
    {
        y<<temp->u<<' '<<temp->v;
        y<<'\n';

        temp=temp->next;
    }

    return 0;
}