#include<iostream>
#include<fstream>
#include<vector>
#define Mmax 400001
#define Nmax 200001
#define INF 10000000
#define pb push_back
#define mp make_pair
using namespace std;

int n,m,h,a,c;
int vizitat[Nmax];

vector <pair<int,int> >lista[Nmax];		// lista de adiacenta;

struct muchie
	{int x,y,c;}Heap[Mmax],A[Nmax];		// Heap-ul + Arborele; 

void citire(char *fisier)				// Citeste Muchiile si costurile lor;
{ifstream f(fisier);
f>>n;									// Numarul de noduri;
f>>m;									// Numarul de muchii;
for(int i=1;i<=m;i++)
	{int x,y,c;
	f>>x>>y>>c;
	lista[x].pb(mp(y,c));
	lista[y].pb(mp(x,c));}
}

void swap(int &i,int &j)
{int aux;
aux=i;
i=j;
j=aux;}

int left(int i) 
{return 2*i;}

int right(int i)
{
	return 2*i+1;}

void heapify(int i,int m)
{
int l=left(i),minim;
int r=right(i);
if ((Heap[l].c<Heap[i].c)&&(l<=m)) minim=l;
	else minim=i;
if ((Heap[r].c<Heap[minim].c)&&(r<=m)) minim=r;
if (minim!=i) { swap(Heap[i].x,Heap[minim].x);
				swap(Heap[i].y,Heap[minim].y);
				swap(Heap[i].c,Heap[minim].c);
				heapify(minim,m);}
}

void BuildMinHeap() 
{int i;
for (i=h/2;i>=1;i--)
	heapify(i,h);
}

void adauga_in_heap(int k)
{for(int i=0;i<lista[k].size();i++)
	if (!vizitat[lista[k][i].first])
		{h++;
		 Heap[h].x=k;
		 Heap[h].y=lista[k][i].first;
		 Heap[h].c=lista[k][i].second;}
}

muchie extrage_min()
{muchie x=Heap[1];
Heap[1]=Heap[h];
h--;
heapify(1,h);
return x;}

void adauga_in_arbore(muchie m)
{a++;
A[a].x=m.x;
A[a].y=m.y;
A[a].c=m.c;}

void Prim(int r)
{
for(int i=1;i<n;i++)
	{vizitat[r]=1;
	adauga_in_heap(r);
	BuildMinHeap();
	muchie m=extrage_min();
	while(vizitat[m.y]) m=extrage_min();
	c=c+m.c;
	adauga_in_arbore(m);
	r=m.y;
	}
}

int main()
{
	citire("apm.in");
	Prim(1);
	ofstream g("apm.out");
	g<<c<<endl;
	g<<a<<endl;
	for(int i=1;i<=a;i++)
		g<<A[i].x<<" "<<A[i].y<<endl;
	return 0;
}