#include <fstream>
#include <queue>
#include <vector>
#define mmax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie { int x,y,cost; }  e[mmax],sol[mmax];
int comp[mmax],n,m,nrsol,cost;

struct cmpf
{
  bool operator() (muchie x,muchie y) 
  {
    return (x.cost>y.cost);
  }
};
  

priority_queue <muchie,vector<muchie>,cmpf> q;


void citire ()
{
  f>>n>>m;
  muchie e;
  for (int i=1; i<=m; i++)
  {
    f>>e.x>>e.y>>e.cost; //e- edge
    q.push(e);
    comp[i]=i; //c - componenta conexa
  }
  f.close ();
}

int find (int x)
{
  int r=x,aux,t;
  while (comp[r]!=r) r=comp[r];
  aux=x;
	while (aux!=r)  
	{
		t=comp[aux];
		comp[aux]=r;
		aux=t;
	}
  return r;
}

void unite (int x,int y)
{
  comp[x]=y;
}

void kruskal ()
{
  muchie mmin;
  while (nrsol!=n-1)
  {
    mmin=q.top (); q.pop ();
    if (find(mmin.x)!=find(mmin.y))
    {
      cost+=mmin.cost;
      unite (find(mmin.x),find(mmin.y));
      sol[++nrsol]=mmin;
    }
  }
}

void afisare ()
{
  g<<cost<<'\n'<<n-1<<'\n';
  for (int i=1; i<=n-1; i++)
    g<<sol[i].x<<" "<<sol[i].y<<'\n';
  g.close ();
}

int main ()
{
  citire ();
  kruskal ();
  afisare ();
  return 0;
}