#include <iostream>
#include <fstream>
#include <limits>
using namespace std;
fstream f("apm.in",ios::in);
fstream g("apm.out",ios::out);
int heap_size,N,pp[200201][2],kk,Q[100000];
double cost;
struct listQ{
   double w;
   int n;
}A[200201];

struct list{
    int v;
    double weight;
    struct list *next;
}*G[200201],*p,*q;
void add(int x,int v,double weight)
{
  list *n= new list;
   n->v=v;
   n->weight=weight;
   if(G[x]!=NULL){
        if(G[x]->weight>weight){
            n->next=G[x];
            G[x]=n;
        }
        else{
            p=G[x];
            while(p->next!=NULL&&p->next->weight<weight)p=p->next;
            n->next=p->next;
            p->next=n;
       }
          }
   else{
       G[x]=n;
       G[x]->next=NULL;
   }
}
void print_G()
{
    for(int i=1;i<=N;i++)
    {
    p=G[i];
    cout<<i<<": ";
    while(p!=NULL){
         cout<<p->v<<","<<p->weight<<" ";
        p=p->next;
    }
    cout<<endl;}
}



void MIN_HEAPIFY(int i);
void exchange(int x,int y);
int LEFT(int i)
{
    return 2*i;
}
int RIGHT(int i)
{
    return 2*i+1;
}
int PARENT(int i)
{
    return i/2;
}
int MAXIMUM()
{
    return A[1].n;
}
int EXTRACT_MIN()
{
    if(heap_size<1)
    {cout<<"\nheap underflow!!!";
        return -1;
    }
    listQ MIN;
    MIN=A[1];
    A[1]=A[heap_size];
    heap_size--;
    MIN_HEAPIFY(1);
    return MIN.n;
}
void DECREASE_KEY(int i, double key)
{
    if(key>A[i].w)
    {  // cout<<key<<" "<<A[i].w<<endl;
       // cout<<"\nNew key is bigger than current key\n";

    }
    else
    {
          int j,ok;
        for(j=1,ok=1;j<=heap_size&&ok;j++)
            if(A[j].n==i)ok=0;
            j--;
        A[j].w=key;
        while(j>1&&A[PARENT(j)].w>A[j].w)
        {
            exchange(j,PARENT(j));
            j=PARENT(j);
        }
    }
}
void INSERT(int key)
{
    heap_size++;
    A[heap_size].w=std::numeric_limits<int>::max();//(1<<31)-1;
    DECREASE_KEY(heap_size,key);
}
void exchange(int x,int y)
{
    listQ aux=A[x];
    A[x]=A[y];
    A[y]=aux;
}
void MIN_HEAPIFY(int i)
{
    int lowest;
    int l=LEFT(i);
    int r=RIGHT(i);
    if(l<=heap_size&&A[l].w<A[i].w)
        lowest=l;
    else
        lowest=i;
    if(r<=heap_size&&A[r].w<A[lowest].w)
            lowest=r;
    if(lowest!=i)
    {
        exchange(i,lowest);
        MIN_HEAPIFY(lowest);
    }
}
void BUILD_MIN_HEAP()
{
    for(int i=heap_size/2;i>=1;i--)
        MIN_HEAPIFY(i);
}
/*
void HEAPSORT()
{
    BUILD_MIN_HEAP();
    for(int i=heap_size;i>=2;i--)
    {
        exchange(1,i);
        heap_size--;
        MIN_HEAPIFY(1);
    }
}*/

void print()
{
    cout<<endl;
    for(int i=1;i<=heap_size;i++)
  {
      cout<<A[i].w<<" ";
    }
    cout<<endl;
}
void init_queue()
{
    for(int i=1;i<=N;i++){
        A[i].w=std::numeric_limits<int>::max();//(1<<31)-1;
        A[i].n=i;
     }
}
int isInA(int k)
{
    return Q[k];
}

void MST_Prim_PQ(int r)
{
    int u;
    init_queue();
    A[r].w=0;
    while(heap_size>0)
    {
        u=EXTRACT_MIN();
        p=G[u];
        Q[u]=0;
        pp[kk][0]=u;
        q=p;
        if(kk>0)
        {
        while(isInA(p->v)){p=p->next;}
        }
      if(kk>0)
        cost+=p->weight;
      pp[kk++][1]=p->v;
           while(q!=NULL){
                if(isInA(q->v))
                    {
                     DECREASE_KEY(q->v,q->weight);}
                     q=q->next;
                    }
   }
}

int main()
{
    int M;
    int x,y;
    double weight;
    f>>N>>M;
    heap_size=N;
for(int i=1;i<=N+1;i++)
    Q[i]=1;

     while (!f.eof())
     {

          f>>x>>y>>weight;
          if(!f.eof()){
          add(x,y,weight);
          add(y,x,weight);
     }}

 // print_G();

     MST_Prim_PQ(N/2);
    // BUILD_MIN_HEAP();
g<<cost<<endl;
g<<N-1<<endl;

 for(int i=1;i<N;i++)
    //if(i!=1)
    g<<pp[i][1]<<" "<<pp[i][0]<<endl;
    return 0;
}