/*
 * Autor: Paul Herman
 * Problema: APM - Prim
 * Data: 06.02.2012
 * Punctaj: -
 * Link: http://www.infoarena.ro/problema/apm
 */
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

#define oo 0x3f3f3f

int n, m;
vector<int> g[200001], c[200001];
int p[200001], h[200001], dh;
int dist[200001], vecin[200001], vecin_ind[200001];
bool apartine[200001];
vector< pair<int, int> > apm;
int cost_apm;

inline void heap_swap(int a, int b)
{
	int t = h[a];
	h[a] = h[b];
	h[b] = t;
	p[h[a]] = a;
	p[h[b]] = b;
}
inline void heap_up(int x)
{
	int tata = (x - 1) / 2;
	while ((tata != x) && (dist[h[x]] < dist[h[tata]]))
	{
		heap_swap(x, tata);
		x = tata;
		tata = (x - 1) / 2;
	}
}
inline void heap_pop()
{
	dh--;
	p[h[dh]] = 0;
	p[h[0]] = -1;
	h[0] = h[dh];
	int mic = 0;
	int modificat;
	int fius, fiud;
	do {
		modificat = mic;
		fius = 2 * modificat + 1;
		fiud = fius + 1;
		if ((fius < dh) && (dist[h[fius]] < dist[h[mic]]))
			mic = fius;
		if ((fiud < dh) && (dist[h[fiud]] < dist[h[mic]]))
			mic = fiud;
		heap_swap(mic, modificat);
	} while (mic != modificat);
}
inline int heap_top()
{
	int top = h[0];
	heap_pop();
	return top;
}
inline void heap_push(int x)
{
	if (p[x] == -1)
	{
		h[dh] = x;
		p[x] = dh;
		dh++;
	}
	heap_up(p[x]);
}
inline void nod_apm(int x)
{
	apartine[x] = true;
	if (vecin[x] > 0)
	{
		apm.push_back(pair<int, int>(x, vecin[x]));
		cost_apm += c[vecin[x]][vecin_ind[x]];
	}
	for (int i = 0; i < g[x].size(); i++)
	{
		if (dist[g[x][i]] > c[x][i])
		{
			dist[g[x][i]] = c[x][i];
			vecin[g[x][i]] = x;
			vecin_ind[g[x][i]] = i;
			if (apartine[g[x][i]] == false)
				heap_push(g[x][i]);
		}
	}
}
inline void citire()
{
	int a, b, cost;
	ifstream fin("apm.in");
	fin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		fin >> a >> b >> cost;
		g[a].push_back(b);
		g[b].push_back(a);
		c[a].push_back(cost);
		c[b].push_back(cost);
	}
	fin.close();
}
inline void scriere()
{
	ofstream fout("apm.out");
	fout << cost_apm << '\n' << apm.size() << '\n';
	for (int i = 0; i < apm.size(); i++)
		fout << apm[i].first << ' ' << apm[i].second << '\n';
	fout.close();
}
inline void prim()
{
	for (int i = 1; i <= n; i++)
	{
		p[i] = -1;
		dist[i] = oo;
		apartine[i] = false;
		vecin[i] = 0;
	}
	dist[1] = 0;
	heap_push(1);
	for (int mi = 1; mi <= n; mi++)
		nod_apm(heap_top());
}
int main()
{
	citire();
	prim();
	scriere();
	return 0;
}