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

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

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

const int Inf = 0x3f3f3f3f;

struct Edge{
	int x, w;
	
	bool operator < (const Edge& e) const
	{
		return w > e.w;
	}
};

int N, M;		// N - nr. de noduri, M - nr. de muchii
VVP G;			// graful initial
VI t;			// t[i] = tata lui i in apm
VP apm;			// lista cu muchiile din apm
int cmin;		// costul minim pentru apm
VB vis;			// vis[i] = true <=> am vizitat nodul i
VI key;

void ReadData();
void Prim(int node);
void WriteGraph();

int main()
{
	ReadData();
	Prim(1);
	
	WriteGraph();
	
	fin.close();
	fout.close();
	return 0;
}

void ReadData()
{
	fin >> N >> M;
	G = VVP(N + 1);
	t = VI(N + 1);
	key = VI(N + 1, Inf);
	vis = VB(N + 1);
	
	int x, y, w;
	while (M--)
	{
		fin >> x >> y >> w;
		
		G[x].push_back({y, w});
		G[y].push_back({x, w});
	}
}

void Prim(int node)
{
	priority_queue<Edge> Q;
	Q.push({node, 0});
	t[node] = -1;
	key[node] = 0;
	
	int x, y, w;
	while (!Q.empty())
	{
		x = Q.top().x;
		vis[x] = true;
		
		if (t[x] != -1)
			apm.push_back({t[x], x});
		cmin += Q.top().w;
		
		for (const auto& p : G[x])
		{
			y = p.first;
			w = p.second;
			
			if (vis[y])
				continue;
			
			if (key[y] > w)
			{
				key[y] = w;
				Q.push({y, w});
				
				t[y] = x;
			}
		}
		
		while (!Q.empty() && vis[Q.top().x])
			Q.pop();
	}
}

void WriteGraph()
{
	fout << cmin << '\n';
	fout << apm.size() << '\n';
	
	for (const auto& p : apm)
		fout << p.first << ' ' << p.second << '\n';
}