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


using namespace std;

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

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

//functii

//void add_to_heap(int number);
void decrease(int poz, int cost);
void init();
void solve();
void afisare();
//void percolate();
//void sift();
void delete_from_heap(int poz);

//declaratii

vector< pair<int, int> > G[maxn];
int H[maxn], C[maxn], Z[maxn], L = 0, SOL = 0, N, M, POZITII[maxn];


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

void init()
{
	fi >> N >> M;
	//cout<<N<<"\n";
	H[1] = 0;
	Z[1] = 1;
	L = N;
	POZITII[1] = 1;
	for (int i = 1;i <= M;i++)
	{
		int x, y, c;
		fi >> x >> y >> c;
		G[x].pb(mkp(y, c));
		G[y].pb(mkp(x, c));
	}
	for (int i = 2;i <= N;i++) Z[i] = POZITII[i] = i, H[i] = INF, C[i] = INF;
}

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

void afisare()
{
	fo << SOL << "\n" << L - 1 << "\n";
	for (int i = 2;i <= L;i++)
		fo << C[i] << " " << i << "\n";
}

void delete_from_heap(int poz)
 {
	H[poz] = H[N];
	Z[POZITII[N]] = Z[POZITII[poz]];
	Z[POZITII[poz]] = INF;
	POZITII[poz] = POZITII[N];
	N--;
	int k = poz;
	if (H[k] < H[k / 2])
		while (H[k] < H[k / 2] && k > 1)
		{
			swap(H[k], H[k / 2]);
			swap(Z[POZITII[k]], Z[POZITII[k / 2]]);
			swap(POZITII[k], POZITII[k / 2]);
			k = k / 2;
		}
	else if (H[k] > H[2 * k] || H[k] > H[2 * k + 1])
		while ((H[k] > H[2 * k] || H[k] > H[2 * k + 1]) && (k<N))
		{
			if (H[2 * k] < H[2 * k + 1])
			{
				swap(H[k], H[2 * k]);
				swap(Z[POZITII[k]], Z[POZITII[2 * k]]);
				swap(POZITII[k], POZITII[2 * k]);
				k = 2 * k;
			}
			else
			{
				swap(H[k], H[2 * k + 1]);
				swap(Z[POZITII[k]], Z[POZITII[2 * k + 1]]);
				swap(POZITII[k], POZITII[2 * k + 1]);
				k = 2 * k + 1;
			}
		}
	return;
}

void decrease(int poz, int cost)
{
	H[poz] = cost;
	int k = poz;
	if (H[k] < H[k / 2])
		while (H[k] < H[k / 2] && k > 1)
		{
			swap(H[k], H[k / 2]);
			swap(Z[POZITII[k]], Z[POZITII[k / 2]]);
			swap(POZITII[k], POZITII[k / 2]);
			k = k / 2;
		}
	else if (H[k] > H[2 * k] || H[k] > H[2 * k + 1])
		while ((H[k] > H[2 * k] || H[k] > H[2 * k + 1]) && (k<N))
		{
			if (H[2 * k] < H[2 * k + 1])
			{
				swap(H[k], H[2 * k]);
				swap(Z[POZITII[k]], Z[POZITII[2 * k]]);
				swap(POZITII[k], POZITII[2 * k]);
				k = 2 * k;
			}
			else
			{
				swap(H[k], H[2 * k + 1]);
				swap(Z[POZITII[k]], Z[POZITII[2 * k + 1]]);
				swap(POZITII[k], POZITII[2 * k + 1]);
				k = 2 * k + 1;
			}
		}
	return;

}