#include<fstream>
#include<queue>
#include<algorithm>
#define NMAX 200005
#define MMAX 400005

using namespace std;

FILE* f=freopen("apm.in","r",stdin);
FILE* o=freopen("apm.out","w",stdout);

struct Edge { int a,b,c; } edges[MMAX];
int n,m;
int totCost;
queue<int> answerIndex;
int parent[NMAX], ranks[NMAX];

bool comp(Edge a, Edge b)
{
	return a.c<b.c;
}

int Find(int x)
{
	if(parent[x]!=x)
		parent[x]=Find(parent[x]);
	return parent[x];
}

void Union(int a, int b)
{
	int aRoot=Find(a);
	int bRoot=Find(b);

	if(aRoot==bRoot) return ;
	if(ranks[aRoot]>ranks[bRoot])
		parent[bRoot]=aRoot;
	else if(ranks[aRoot]>ranks[bRoot])
		parent[aRoot]=bRoot;
	else
		parent[bRoot]=aRoot, ranks[aRoot]+=1;
}

void Kruskal()
{
	for(int i=0;i<m;++i)
	{
		Edge edg=edges[i];
		int rootA=Find(edg.a);
		int rootB=Find(edg.b);
		if(rootA!=rootB)
		{
			Union(rootA,rootB);
			answerIndex.push(i);
			totCost+=edg.c;
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);

	for(int i=0;i<m;++i)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		edges[i].a=x;
		edges[i].b=y;
		edges[i].c=c;
	}

	for(int i=1;i<=n;++i)
		parent[i]=i;

	sort(edges,edges+m,comp);

	Kruskal();
	int num=answerIndex.size();
	printf("%d\n%d\n",totCost,num);

	while(num)
	{
		int ind=answerIndex.front();
		answerIndex.pop();
		num-=1;
		printf("%d %d\n",edges[ind].a,edges[ind].b);
	}

	return 0;
}