#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define mkp make_pair

using namespace std;

const int maxn = 200200;
const int INF = 200000200;

int VEC[maxn], ANS, V[maxn], H[maxn * 2 + 100], POZ[maxn];
vector <pair<int, int> > VECT[maxn], VANS;
int N, M, L, C[maxn];

void introduce_in_apm(int x)
{
	for (unsigned int i = 0; i < VECT[x].size(); ++i)
	{
		int nod = VECT[x][i].first;
		int cost = VECT[x][i].second;
		V[nod] = min(V[nod], cost);
		if (V[nod] == cost) VEC[nod] = x;
	}
}

void push(int poz)
{
	while ((poz * 2 <= L && V[H[poz]] > V[H[poz * 2]]) || (poz * 2 + 1 <= L && V[H[poz]] > V[H[poz * 2 + 1]]))
	{
		if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)
		{
			swap(H[poz], H[poz * 2]);
			swap(POZ[H[poz]], POZ[H[poz * 2]]);
			poz *= 2;
		}
		else
		{
			swap(H[poz], H[poz * 2 + 1]);
			swap(POZ[H[poz]], POZ[H[poz * 2 + 1]]);
			poz = poz * 2 + 1;
		}
	}
}


void pop(int poz)
{
	while (poz > 1 && V[H[poz]] < V[H[poz / 2]])
	{
		swap(H[poz], H[poz / 2]);
		swap(POZ[H[poz]], POZ[H[poz / 2]]);
		poz = poz / 2;
	}
}

void introduce_in_heap(int nod)
{
	H[++L] = nod;
	POZ[nod] = L;
	pop(L);
}

int scoate_radacina_heap()
{
	int x = H[1];
	swap(H[1], H[L]);
	swap(POZ[H[1]], POZ[H[L]]);
	L--;
	push(1);
	POZ[x] = 0;
	return x;
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d\n", &N, &M);
	for (int i = 1; i <= M; ++i)
	{
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		VECT[x].pb(mkp(y, c));
		VECT[y].pb(mkp(x, c));
	}

	for (int i = 1; i <= N; ++i) V[i] = INF;
	V[1] = 0;
	introduce_in_apm(1);
	for (int i = 2; i <= N; ++i)
	{
		introduce_in_heap(i);
	}
	for (int i = 1; i < N; ++i)
	{
		int x = scoate_radacina_heap();
		introduce_in_apm(x);
		ANS += V[x];
		VANS.pb(mkp(x, VEC[x]));
		for (unsigned int j = 0; j < VECT[x].size(); ++j)
		{
			int nod = VECT[x][j].first;
			if (POZ[nod]) pop(POZ[nod]);
		}
	}
	printf("%d\n", ANS);
	printf("%d\n", N - 1);
	for (unsigned int i = 0; i < N - 1; ++i)
		printf("%d %d\n", VANS[i].first, VANS[i].second);
	return 0;
}