#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

ifstream fi("apm.in");
ofstream fo("apm.out");

inline int father(int nod) {
	return nod / 2;
}

inline int left_son(int nod) {
	return nod * 2;
}

inline int right_son(int nod) {
	return nod * 2 + 1;
}

#define pb push_back
#define INF 202002312
#define maxn 200200
#define mkp make_pair

struct heap {
	int cost, nod;
} H[maxn];

int Z[maxn], cmin[maxn], POZ[maxn], N, M, L, first_node, ANS = 0;
vector< pair<int, int> > V[maxn];

inline int min() {
	return H[1].cost;
}

void percolate(int K);
void sift(int K);
void delete_from_heap(int K);
void decrease(int K, int val);
void insert_to_heap(int key);
void solve();
void init();
void afisare();


int main()
{
	init();
	solve();
	afisare();
}

void sift(int K) {
	int son;
	do {
		son = 0;
		if (left_son(K) <= N) {
			son = left_son(K);
			if (right_son(K) <= N && H[right_son(K)].cost < H[left_son(K)].cost) {
				son = right_son(K);
			}
			if (H[son].cost > H[K].cost) {
				son = 0;
			}
		}

		if (son) {
			Z[H[K].nod] = K;
			Z[H[son].nod] = son;
			swap(H[K], H[son]);
			swap(Z[H[K].nod], Z[H[son].nod]);
			K = son;
		}
	} while (son);
}

void percolate(int K) {
	heap key = H[K];
	int keyz = Z[H[K].nod];

	while ((K > 1) && (key.cost < H[father(K)].cost)) {
		H[K] = H[father(K)];
		Z[H[K].nod] = K;
		K = father(K);
	}

	H[K] = key;
	Z[H[K].nod] = K;

}

void delete_from_heap(int K) {
	Z[H[K].nod] = INF;
	H[K] = H[N];
	Z[H[K].nod] = K;
	H[N] = { 0,0 };
	--N;

	if ((K > 1) && (H[K].cost < H[father(K)].cost)) {
		percolate(K);
	}
	else {
		sift(K);
	}
}

void decrease(int K, int val) {
	H[K].cost = val;

	if ((K > 1) && (H[K].cost < H[father(K)].cost)) {
		percolate(K);
	}
	else {
		sift(K);
	}
}

void insert_to_heap(int key) {
	H[++N].cost = key;
	percolate(N);
}

void init()
{
	fi >> N >> M;
	for (int i = 1;i <= M;i++)
	{
		int x, y, c;
		fi >> x >> y >> c;
		V[x].pb(mkp(y, c));
		V[y].pb(mkp(x, c));
	}

	for (int i = 1;i <= N;i++)
		H[i].cost = INF, Z[i] = i, H[i].nod = i;
	H[1].cost = 0;
	L = N;
}

void solve()
{
	for (int i = 1;i <= L;i++)
	{
		int node = H[1].nod;
		ANS += H[1].cost;
		delete_from_heap(1);
		for (int j = 0;j < V[node].size();j++)
		{
			int vecin, cost;
			vecin = V[node][j].first;
			cost = V[node][j].second;
			int pos = Z[vecin];
			if (pos != INF && H[pos].cost >= cost)
				decrease(pos, cost), cmin[vecin] = node;
		}	
	}
}

void afisare()
{
	fo << ANS << endl << L - 1 << endl;
	for (int i = 1;i <= L;i++)
		if (cmin[i] != 0) fo << cmin[i] << " " << i << endl;
}