#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; }
}

void unire(int x, int y)
{
	int i, tapa;
	tapa = GR[x];
	for (i = 1; i <= m; ++i)
		if (GR[i] == tapa) GR[i] = GR[y];
}

void solve ()
{
	int i;
	sort(index+1, index+m+1, cmp);
	for (i = 1; i <= m; ++i)
		if ( GR[ X[index[i]] ] != GR[ 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;
}