#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;

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


struct edge
{
	int n, cost;
};

struct compare
{
	bool operator () (const edge& a, const edge& b)
	{
		return a.cost > b.cost;
	}
};

void Prim(vector<vector<edge>>& graf, int n,int src)
{
	int sum = 0;
	priority_queue<edge, vector<edge>, compare>pq;
	vector<int>parent(n + 1, -1);
	vector<int>key(n + 1, INT_MAX);
	vector<bool>inMST(n + 1, false);
	key[src] = 0;
	pq.push({ src,key[src] });
	while (!pq.empty())
	{
		int u = pq.top().n;
		
		pq.pop();
		inMST[u] = true;

		for (int i = 0; i < graf[u].size(); i++)
		{
			int v = graf[u][i].n;
			int cost = graf[u][i].cost;
			if (!inMST[v] and cost < key[v])
			{
				key[v] = cost;
				pq.push({ v,key[v] });
				parent[v] = u;
				
			}
		}
	}
	for (int i = 1; i <= n; i++)
		if(inMST[i])
		sum += key[i];
	g << sum << "\n";
	g << n - 1 << "\n";
	for (int i = 2; i <= n; i++)
		g << parent[i] << " " << i << "\n";
}

int main()
{

	int n, m;
	f >> n >> m;
	vector<vector<edge>>graf(n + 1);
	for (int i = 1; i <= m; i++)
	{
		int x, y, z;
		f >> x >> y >> z;
		graf[x].push_back({ y,z });
		graf[y].push_back({ x,z });
	}
	Prim(graf, n, 1);
	return 0;
}