#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 nod, 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>dist(n + 1, INT_MAX);
	vector<bool>inMST(n + 1, false);
	dist[src] = 0;
	pq.push({ src,dist[src] });
	while (!pq.empty())
	{
		int u = pq.top().nod;

		pq.pop();
		if (!inMST[u])
		{
			inMST[u] = true;

			for (int i = 0; i < graf[u].size(); i++)
			{
				int v = graf[u][i].nod;
				int cost = graf[u][i].cost;
				if (!inMST[v] and cost < dist[v])
				{
					dist[v] = cost;
					pq.push({ v,dist[v] });
					parent[v] = u;

				}
			}
		}
	}
	for (int i = 1; i <= n; i++)
		if(inMST[i])
		sum += dist[i];
	g << sum << "\n";
	g << n - 1 << "\n";
	for (int i = 2; i <= n; i++)
		g << parent[i] << " " << i << "\n";
}
void justdo()
{
    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);
}
int main()
{

    justdo();
	return 0;
}