#include <stdio.h>
#include <fstream.h>
#define r 400001
ifstream fin("apm.in");
FILE *g=fopen ("apm.out", "w");
struct muchie { int x,y,c; } H[r],t;
int L[r/2],sol[r];
int n,m,i,S;
long long cost;

void swap (muchie &a, muchie &b)
{
	t=a;
	a=b;
	b=t;
}

void citire() {
int i;
fin>>n>>m;
for (i=1;i<=n;i++)
	L[i]=i;
for (i=1;i<=m;i++)
	fin>>H[i].x>>H[i].y>>H[i].c;
}

void downheap(int m, int x) {
int fiu;
do
{
	fiu=0;
	if (2*x<=m)								fiu=2*x;
	if (2*x+1<=m && H[fiu+1].c>H[fiu].c)	fiu=2*x+1;
	if (H[x].c>=H[fiu].c)						fiu=0;
	
	if (fiu)
	{
		swap (H[fiu], H[x]);
		x=fiu;
	}
}
while (fiu);
}
	
void build_heap() 
{
for (int i=m/2;i>=1;i--)
	downheap(m, i);
}

void heap_sort() {
build_heap();
for (int i=m;i>=2;i--)
{
	swap (H[1], H[i]);
	downheap(i-1, 1);
}
}

void change(int a, int b) {
int i;
for (i=1;i<=n;i++)
	if (L[i]==a)
		L[i]=b;
}
	

int main() {
citire();
heap_sort();

for (i=1;i<=m-1;i++)
	if (L[H[i].x]!=L[H[i].y])
	{
		change (L[H[i].y], L[H[i].x]);
			
		sol[++S]=i;
		cost+=H[i].c;
	}
	
fprintf (g, "%lld\n%d\n", cost,S);
for (i=1;i<=S;i++)
	fprintf (g, "%d %d\n", H[sol[i]].x, H[sol[i]].y);
return 0;
}