#include <cstdio>
#include <algorithm>

using namespace std;

const int Nmax = 200005;
const int Mmax = 400005;

struct Edge {
	int x,y,c,g;
}; 

int N,M;
Edge edges[Mmax];
int disjoint[Nmax];
int sol = 0;

int findHead(int a)
{
	if (!disjoint[a])
		return a;
	int head=a;
	while (disjoint[head] != 0) 
		head = disjoint[head];
	disjoint[a] = head;
	return head;
}

int areDisjoint(int a,int b)
{
	int heada = a,headb = b;
	for(; disjoint[heada] ; heada = disjoint[heada]);
	for(; disjoint[headb] ; headb = disjoint[headb]);
	if (heada == headb)
		return 0;
	return 1;
}

void unite(int a,int b)
{
	int heada = a,headb = b,aux,auxheada;
	for(; disjoint[heada] ; heada = disjoint[heada]);

	auxheada = a;
	while (disjoint[auxheada])
	{
		aux = disjoint[auxheada];
		disjoint[auxheada] = heada;
		auxheada = aux;
	}
	while (disjoint[headb])
	{
		aux = disjoint[headb];
		disjoint[headb] = heada;
		headb = aux;
	}
	disjoint[headb] = heada;
}

void solve()
{
	for(int j=0;(unsigned int)j < M; ++j)
		if (areDisjoint( edges[j].x , edges[j].y ))
		{
			unite( edges[j].x , edges[j].y );
			sol += edges[j].c;
			edges[j].g = 1;
		}
}

bool cmp(Edge e1,Edge e2)
{
	return (e1.c < e2.c);
}

void sortV()
{
	sort(edges+0,edges+M,cmp);
}

void readV()
{
	scanf("%d",&N);
	scanf("%d",&M);
	for(int i=0;i<M;++i)
	{
		scanf("%d",&edges[i].x);
		scanf("%d",&edges[i].y);
		scanf("%d",&edges[i].c);
		edges[i].g = 0;
	}
}

void printSol()
{
	printf("%d\n%d\n",sol,N-1);
	for(int i=0;i < M;++i)
		if (edges[i].g)
			printf("%d %d\n",edges[i].x,edges[i].y);
	printf("\n");
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);

	readV();
	sortV();
	solve();
	printSol();
	return 0;
}