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

int N, M,s;

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

#define MAX 200010

typedef pair<int, int> Node;

#define p first
#define c second

int T[MAX];

vector<Node> G[MAX];
vector<Node> P;

int v[MAX];

struct compare
{
	bool operator ()(const Node &p1, const Node &p2)
	{
		return p1.c > p2.c;
	}
};

priority_queue<Node, vector<Node>, compare> PQ;

void Prim(int S)
{
	v[S] = 1<<31;
	for (int i = 0;i < G[S].size();++i)
		PQ.push(make_pair(G[S][i].p, G[S][i].c)), T[G[S][i].p] = S,v[G[S][i].p]= G[S][i].c;

	while (PQ.size())
	{
		Node node = PQ.top();
		PQ.pop();

		if (v[node.p] != 1<<31)
		{
			s += node.c;
			P.push_back(make_pair(T[node.p], node.p));
			v[node.p] = 1<<31;
		}
		else
			continue;

		for (int i = 0;i < G[node.p].size();++i)
		{
			if (v[G[node.p][i].p]>G[node.p][i].c)
				PQ.push(make_pair(G[node.p][i].p, G[node.p][i].c)), v[G[node.p][i].p]= G[node.p][i].c, T[G[node.p][i].p] = node.p;
		}
	}
}

int main()
{
	in >> N >> M;

	for (int i = 1;i <= N;++i)
		v[i] = (1 << 30);
	
	for (int i = 1;i <= M;++i)
	{
		int a, b, cost;
		in >> a >> b >> cost;
		G[a].push_back(make_pair(b, cost));
		G[b].push_back(make_pair(a, cost));
	}
	
	Prim(1);

	out << s<<'\n';

	out << P.size() << '\n';

	for (int i = 0;i < P.size();++i)
		out << P[i].p << " " << P[i].c << "\n";
	

	return 0;
}