#include <fstream>
#include <vector>
using namespace std;

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

const int N = 2e5 + 1;
const int INF = 2e8 + 1;

int vec[N], rez , V[N], h[N * 2 + 100], poz[N];
vector <pair <int,int>> G[N], Vrez;
int n, m, L;

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

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

void sterge(int p)
{
	while(p > 1 && V[h[p]] < V[h[p / 2]])
	{
		swap(h[p], h[p / 2]);
		swap(poz[h[p]], poz[h[p / 2]]);
		p /= 2;
	}
}

void adauga_in_heap(int nod)
{
	h[++L] = nod;
	poz[nod] = L;
	sterge(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()
{
	in >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int x, y, c;
		in >> x >> y >> c;
		G[x].push_back(make_pair(y , c));
		G[y].push_back(make_pair(x , c));
	}

	for(int i = 1; i <= n; i++) V[i] = INF;
	V[1] = 0;
	adauga_in_apm(1);

	for(int i = 2; i <= n; i++) adauga_in_heap(i);

	for(int i = 1; i < n; i++)
	{
		int x = scoate_radacina_heap();
		adauga_in_apm(x);
		rez += V[x];
		Vrez.push_back(make_pair(x, vec[x]));
		for(unsigned int j = 0; j < G[x].size(); j++)
		{
			int nod = G[x][j].first;
			if (poz[nod])
			{
			    sterge(poz[nod]);
			}
		}
	}

    out << rez << "\n" << n - 1 << "\n";

	for(int i = 0; i < n - 1; i++)
		out << Vrez[i].first << " " << Vrez[i].second << "\n";

	return 0;
}