#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define punct pair<int,int>
#define nod first
#define cos second
#define mmax 400005

int n, m, sum;
int GR[mmax], index[mmax], X[mmax], Y[mmax], cos[mmax];
vector<int> vec;

bool cmp (int a, int b) { return cos[a]<cos[b]; }

void citire ()
{
	int i;
	freopen("apm.in","r",stdin);
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; ++i) { scanf("%d%d%d", &X[i], &Y[i], &cos[i]); index[i] = i; GR[i] = i; }
}

int grupa(int i)
{
	if (GR[i] == i) return i;
	GR[i] = grupa(GR[i]);
	return GR[i];
}

void unire(int i,int j)
{
	GR[grupa(i)] = grupa(j); 
}


void solve ()
{
	int i;
	sort(index+1, index+m+1, cmp);
	for (i = 1; i <= m; ++i)
		if ( grupa( X[index[i]] ) != grupa( Y[index[i]] ) )
		{
			sum += cos[index[i]];
			unire(X[index[i]],Y[index[i]]);
			vec.push_back (index[i] );
		}
}

void afisare ()
{
	int i;
	freopen("apm.out","w",stdout);
	printf("%d\n%d\n", sum, n-1);
	for(i = 0;i < n - 1; ++i)
		printf("%d %d\n", X[vec[i]], Y[vec[i]]);
}
	
int main ()
{
	citire ();
	solve ();
	afisare ();
	return 0;
}