#include<cstdio>
#include<vector>
#include<algorithm>
#define aa first
#define bb second

using namespace std;

const int N=200002;

int n, m, rang[N], root[N], rez, num;

bool ok[N];

vector < pair< int, pair <int,int> > > g;

void Read()
{
	int a, b, c;
	
	scanf( "%d%d", &n, &m);
	
	for( int i=1; i<=m; ++i)
	{
		scanf( "%d%d%d", &a, &b, &c);
		g.push_back(make_pair(c,make_pair(a,b)));
	}
	
	sort( g.begin(), g.end());
}

int GetRoot(int i)
{
	if(root[i]!=i)
		root[i]=GetRoot(root[i]);
	return root[i];
}

void Solve()
{
	int a, b;
	for(int i=1; i<=n; ++i)
		root[i]=i,rang[i]=1;
	
	for( int i=0; i<m; ++i)
		if(GetRoot(g[i].bb.aa)!=GetRoot(g[i].bb.bb))
		{
			rez+=g[i].aa;
			num++;
			ok[i]=1;
			a=root[g[i].bb.aa];
			b=root[g[i].bb.bb];
			if(rang[a]<rang[b])
			{
				root[a]=b;
				rang[b]+=rang[a];
			}
			else
			{
				root[b]=a;
				rang[a]+=rang[b];
			}
		}
}

void Print()
{
	printf( "%d\n%d\n", rez, num);
	for( int i=0; i<m; ++i)
		if(ok[i])
			printf("%d %d\n", g[i].bb.aa, g[i].bb.bb);
}

int main()
{
	freopen( "apm.in", "r", stdin);
	freopen( "apm.out", "w", stdout);
	
	Read();
	Solve();
	Print();
	
	return 0;
}