//prim with heap
#include<fstream.h>
#define inf 10000
#define nx 200005
#define mx 400005
struct gf
 {
  int nod,cost;
  gf *next;
 };
gf *a[nx];
struct el
 {
  int x,y,c;
 };
el heap[mx],rez[mx];
int n,m,L,viz[nx];

void push_up(int x)
 {
  el aux;
  while (x/2 && heap[x].c<heap[x/2].c)
    {
     aux=heap[x];
     heap[x]=heap[x/2];
     heap[x/2]=aux;
     x/=2;
    }
 }

void push_heap (int x,int y,int cost)
 {
  heap[++L].x=x,heap[L].y=y,heap[L].c=cost;
  push_up(L);
 }

void push_down(int x)
 {
  int y=0;
  el aux;
  while (y!=x)
   {
    if (y*2<=L && heap[x].c>heap[y*2].c)
      x=y*2;
    if (y*2+1<=L && heap[x].c>heap[y*2+1].c)
      x=y*2+1;
    aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;
   }
 }

void pop_heap()
 {
  heap[1]=heap[L--];
  push_down(1);
 }

int main()
 {
  ifstream be ("apm.in");
  ofstream ki ("apm.out");
  int i,x,y,z,poz,min=inf;
  be>>n>>m;
  for (i=1;i<=m;++i)
   {
    be>>x>>y>>z;
    gf *q=new gf;
    if (z<min) min=z,poz=x;
    q->cost=z,q->nod=y;
    q->next=a[x];
    a[x]=q;
    q=new gf;
    q->cost=z,q->nod=x;
    q->next=a[y];
    a[y]=q;
   }
  be.close();
  for (gf *p=a[poz];p;p=p->next)
    push_heap(poz,p->nod,p->cost);
  viz[poz]=1;
  int sz=0,s=0;
  while (L && sz<n-1)
   {
    while (viz[heap[1].x] && viz[heap[1].y]) pop_heap();
    rez[++sz]=heap[1];
    poz=heap[1].x;
    if (viz[poz]) poz=heap[1].y;
    viz[poz]=1;
    s+=heap[1].c;
    pop_heap();
    for (gf *p=a[poz];p;p=p->next)
      push_heap(poz,p->nod,p->cost);
   }
  ki<<s<<'\n'<<sz<<'\n';
  for (i=1;i<=sz;++i)
   ki<<rez[i].x<<" "<<rez[i].y<<'\n';
  ki.close();
  return 0;
 }