#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], ind[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]); ind[i] = i; GR[i] = i; }
}

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

void unire(int x,int y)
{
	GR[grupa(x)] = grupa(y); 
}


void solve ()
{
	int i;
	sort(ind+1, ind+m+1, cmp);
	for (i = 1; i <= m; ++i)
		if ( grupa( X[ind[i]] ) != grupa( Y[ind[i]] ) )
		{
			sum += cos[ind[i]];
			unire(X[ind[i]],Y[ind[i]]);
			vec.push_back (ind[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;
}