#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n, m;
int suma = 0;

const int NMAX = 200005;

int tati[NMAX];

struct edge
{
	int x, y, cost;
};

vector <edge> graf;
vector <pair <int, int> > Sol;

void initTati(int x)
{
	for(int i = 1; i <= x; i++)
		tati[i] = i;
}

void citire()
{
	in >> n >> m;
	
	initTati(n);
	
	for(int i = 0; i < m; i++)
	{
		int a, b, c;
		in >> a >> b >> c;
		graf.push_back({a, b, c});
	}
}

bool cmp(const edge &a, const edge &b)
{
	return a.cost < b.cost;
}

int getRoot(int nod)
{
	if(nod == tati[nod])
		return nod;
	return( tati[nod] = getRoot(tati[nod]) );
}

bool areUnited(int x, int y)
{
	return getRoot(x) == getRoot(y);
}

void unite(int x, int y)
{
	tati[getRoot(x)] = getRoot(y);
}

void solve()
{
	sort(graf.begin(), graf.end(), cmp);
	/*for(int i = 0; i < graf.size(); i++)
	{
		cout << graf[i].x << " " << graf[i].y << " " << graf[i].cost << "\n";
		
	}*/
	for(edge e : graf)
	{
		if(!areUnited(e.x, e.y))
		{
			unite(e.x, e.y);
			Sol.push_back(make_pair(e.y, e.x));
			suma += e.cost;
		}
	}
}
int main()
{
	citire();
	solve();
	out << suma << "\n";
	out << Sol.size()<< "\n";
	for(auto e : Sol)
	{
		out << e.first << " " << e.second << "\n";
	}
	return 0;
}