#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
 struct muchie
 {int x,y,cost;};

 struct cmp
 {
  bool operator() (muchie a,muchie b)
   {
      return a.cost>b.cost;
   }
 };

 int n,m,k,use[200005],mx[200005],my[200005],sol=0;

 vector <muchie> v[200005];
 priority_queue <muchie,vector <muchie>,cmp> heap;

muchie el,nod;

int main()
{ int i,j,x,y,cost;
    f>>n>>m;
    for(i=1;i<=m;i++)
     { f>>x>>y>>cost;
         el.x=x; el.y=y; el.cost=cost;
         v[x].push_back(el);
         el.x=y; el.y=x;
         v[y].push_back(el);
     }


      el.x=0; el.y=1; el.cost=0;
     heap.push(el);
     while(!heap.empty())
     { nod=heap.top(); heap.pop();

       if (!use[nod.y])
       { use[nod.y]=1;
         if (nod.x) {k++; mx[k]=nod.x; my[k]=nod.y; sol+=nod.cost;}

       for(i=0;i<v[nod.y].size();i++)
       { el.x=nod.y;
         el.y=v[nod.y][i].y;
         el.cost=v[nod.y][i].cost;
         heap.push(el);

       }

       }

     }
      g<<sol<<"\n"<<k<<"\n";
     for(i=1;i<=k;i++)
      g<<mx[i]<<" "<<my[i]<<"\n";
    return 0;
}