#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#define N 100005
using namespace std;

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



int nrc;
int nivel[N];
int nma[N]; //nivel minim accesibil
int nrm_apm;


class Graph {


public:
	static bool viz[N];
	static bool viz_t[N];
	//int cost[N];
	stack <int> S;
	int n; //nr de varfuri
	int m; //nr de muchii
	

	vector <int> a[N];
	vector <int> c[N];
	vector <int> a_t[N];
	int h[N], tata[N];
	int cost[N];
	
	//pt apm
	
	vector<pair<pair<int, int>, int>> a_cost; //((nod1, nod2), cost) asa retin costul fiecarei muchii
	vector<pair<int, int>>apm;
	



	Graph(int n, int m)
	{
		this->n = n;
		this->m = m;
		
	}

	void Citire_orientat();
	void Citire_neorientat();
	void Citire_neorientat_cost();
	void DFS(int x);
	void DFS_T(int x, int ct);
	void CompTConexe();
	void ParcurgereGraf();
	void BFS(int x);
	void SortTop();
	void Kruskal();
	int Find(int x);
	void Union(int rx, int ry);
	
	


};

bool Graph::viz[N] = { 0 };
bool Graph::viz_t[N] = { 0 };



void Graph::Citire_orientat()
{
	int i;
	int x, y;

	for (i = 0; i < m; i++)
	{
		fin >> x >> y;
		a[x].push_back(y);
		a_t[y].push_back(x);

	}
}

void Graph::Citire_neorientat()
{
	int i;
	int x, y;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		
	}
}
void Graph::Citire_neorientat_cost()
{
	int i;
	int x, y, z;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> z;
		a_cost.push_back(make_pair(make_pair(x, y), z));
		
	}
	
}
void Graph::BFS(int x)
{
	queue <int> q;
	int k, i;
	viz[x] = 1;
	cost[x] = 0;
	q.push(x);

	while (!q.empty())
	{
		k = q.front();
		for (i = 0; i < a[k].size(); i++)
			if (!viz[a[k][i]])
			{
				q.push(a[k][i]);
				viz[a[k][i]] = 1;
				cost[a[k][i]] = cost[k] + 1;
			}

		q.pop();
	}

	for (i = 1; i <= n; i++)
		if (viz[i] == 0)
			fout << -1 << " ";
		else fout << cost[i] << " ";



}
void Graph::ParcurgereGraf()
{
	int i;
	for (i = 1; i <= n; i++)
		if (!viz[i])
			DFS(i);
}

void Graph::DFS(int x)
{
	int i;
	viz[x] = 1;
	for (i = 0; i < a[x].size(); i++)
		if (!viz[a[x][i]])
			DFS(a[x][i]);
	S.push(x);
}
void Graph::SortTop()
{
	int i;
	for (i = 1; i <= n; i++)
		if (!viz[i])
			DFS(i);
	while (!S.empty())
	{
		fout << S.top() << " ";
		S.pop();
	}
}


void Graph::DFS_T(int x,int ct)
{
	int i;
	viz_t[x] = 1;
	c[ct].push_back(x); //pt fiecare nod, din ce comp tconexa face parte
	for (i = 0; i < a_t[x].size(); i++)
		if (viz_t[a_t[x][i]] == 0)
			DFS_T(a_t[x][i], ct);
}

/*
void Graph::CompTConexe()
{
	int i, j, x, ct = 0;
	while (!S.empty())
	{
		x = S.top();
		S.pop();
		if (viz_t[x] == 0)
		{
			ct++;
			DFS_T(x, ct);
		}

	}
	fout << ct << "\n";
	for (i = 1; i <= ct; i++)
	{
		for (j = 0; j < c[i].size(); j++)
			
				fout << c[i][j] << " ";
		fout << "\n";
	}

}*/

bool criteriu_sortare(const pair<pair<int, int>,int>&cost1, const pair<pair<int, int>,int >&cost2)
{
	return cost1.second < cost2.second;
}

int Graph::Find(int x)
{
	if (x == tata[x])
		return x;
	return Find(tata[x]);
}

void Graph::Union(int x, int y)
{
	int rx = Find(x);
	int ry = Find(y);

	if (h[rx] < h[ry])
	{
		h[ry] += h[rx];
		tata[rx] = ry;
		nrm_apm++;
		
	}
	else
	{
		h[rx] += h[ry];
		tata[ry] = rx;
		nrm_apm++;
	}
}
void Graph::Kruskal()
{
	int cost_total = 0;
	int i;
	int cx, cy;
	

	


	//pentru fiecare nod initializez vectorul de tata si de inaltime
	for (i = 1; i <= n; i++)
	{
		tata[i] = i;
		h[i] = 1;

	}
	//sortam vectorul de muchii ca sa facem apoi partea de greedy
	//folosim criteriul definit mai sus

	sort(a_cost.begin(), a_cost.end(), criteriu_sortare);

	for (i = 1; i <= m; i++)
	{
		//gasesc cel mai indepartat stramos al fiecarui nod din muchia i
		cx = Find(a_cost[i].first.first);
		cy = Find(a_cost[i].first.second);

		if (cx != cy)
		{
			//e bun, inseamna ca nu formeaza cicluri deci o pastram in apm

			apm.push_back(make_pair(a_cost[i].first.first, a_cost[i].first.second));
			
			cost_total += a_cost[i].second;
			Union(a_cost[i].first.first, a_cost[i].first.second);

		}


	}
	fout << cost_total << "\n";
	fout << nrm_apm << "\n";
	for (i = 0; i < nrm_apm; i++)
		fout << apm[i].first << " " << apm[i].second << "\n";

}
/*
void Graph::DFSB(int k, int tata)
{
	viz[k] = 1;
	nivel[k] = nivel[tata] + 1;
	S.push(k);
	for (int i = 1; i <= a[k].size(); i++)
	{
		if (a[k][i] != tata)
			if (viz[a[k][i]])
			{
				if (nma[k] > nivel[i])
					nma[k] = nivel[i];
			}
			else
			{
				DFSB(i, k);
				if (nma[k] > nma[i])
					nma[k] = nma[i];

				//determinare pct art
				if(nivel[k] <= nma[i] && k != )
			}


	}

	
}*/

int main()
{
	int n, m;

	fin >> n >> m;
	Graph g(n, m);
	g.Citire_neorientat_cost();

	

	g.Kruskal();







	return 0;
}