/* Algoritmul lui Prim
 * O(m * log m)
 * 
 * Se alege un nod arbitrar S si se introduce in arbore.
 * Se asociaza fiecarui nod x, cate o cheie key[x] = oo
 * key[S] = 0;
 * 
 * La fiecare pas, se examineaza fiecare muchie incidenta arborelui,
 * si se alege "muchia usoara", adica muchia de cost (cheie) minim
 * care are un capat in arbore
 */ 
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#include <tuple>
using namespace std;

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

const int Inf = 0x3f3f3f3f,
	      MaxN = 200001;

struct Edge {
	Edge() : node {0}, key {0}
	{}
	Edge(int node, int key) : 
		node {node}, key {key}
	{}
	
	bool operator < (const Edge& e) const
	{
		return key > e.key;
	}
	int node, key;
};

using VI  = vector<int>;
using VP  = vector<pair<int, int>>;
using VVP = vector<VP>;

int n;
bitset<MaxN> v; // v[x] = 1 (daca nodul x 
				// a fost adaugat la arbore 
				// deci daca a iesit din coada
VVP G;  // graful
VP apm; // retine muchiile APM-ului
VI key;
long long cost_apm;

void ReadGraph();
void Prim(int x); 
void WriteAPM();

int main()
{
	ReadGraph();
	Prim(1);
	WriteAPM();
}
 
void ReadGraph()
{
	int a, b, w, m;
	fin >> n >> m;
	G = VVP(n + 1);
	
	while (m--)
	{
		fin >> a >> b >> w;
		G[a].emplace_back(b, w);
		G[b].emplace_back(a, w);
	}
}

void Prim(int x)
{
	priority_queue<Edge> Q;
	key = VI(n + 1, Inf);
	VI t   = VI(n + 1); // retine APM
	
	int y, ky; // ky = cheia lui y
	key[x] = 0;
	Q.emplace(x, 0);
	
	while (!Q.empty())
	{
		x = Q.top().node;
		v[x] = 1;
		
		for (auto& p : G[x])
		{
			tie(y, ky) = p;			
			if (v[y]) continue;
			if (key[y] > ky)
			{
				key[y] = ky;
				t[y] = x;
				Q.emplace(y, key[y]);
			}
		}
		
		apm.emplace_back(x, t[x]);
		cost_apm += key[x];
		while (!Q.empty() && v[Q.top().node])
			Q.pop();
	}
}

void WriteAPM()
{
	fout << cost_apm << '\n'
		 << apm.size() - 1 << '\n';
	
	for (size_t i = 1; i < apm.size(); ++i)
		fout << apm[i].first << ' ' << apm[i].second << '\n';
}