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

ifstream in("apm.in");
ofstream out("apm.out");
struct Edge
{
	int adj_node, cost;
};
typedef vector < vector<Edge>> Graph;


class DisjointSet
{
	vector<int> p;
	vector<int> rang;
public:
	DisjointSet(int n) : p(n, 0), rang(n, 0)
	{
		for (int i = 0; i < n; i++)
			p[i] = i;
	}
	int Find(int x)
	{
		if (p[x] != x)
			p[x] = Find(p[x]);
		return p[x];
	}
	void Union(int x, int y)
	{
		int px = Find(x);
		int py = Find(y);
		if (rang[px] > rang[py])
		{
			p[py] = px;
		}
		else if (rang[px] < rang[py])
		{
			p[px] = py;
		}
		else
		{
			p[py] = px;
			rang[px]++;
		}
	}
};

void Kruskal(Graph& G)
{
	vector<pair<int, pair<int, int>>> edges;
	vector<pair<int, int>> picked_edges;
	for (int i = 0; i < G.size(); i++)
	{
		for (auto it = G[i].begin(); it != G[i].end(); it++)
		{
			if (i < it->adj_node) edges.push_back({ it->cost, { i, it->adj_node } });
		}
	}
	DisjointSet dset(G.size());
	sort(edges.begin(), edges.end());
	int sum = 0;
	for (auto ed = edges.begin(); ed != edges.end(); ed++)
	{
		if (dset.Find(ed->second.first) != dset.Find(ed->second.second))
		{
			dset.Union(ed->second.first, ed->second.second);
			picked_edges.push_back({ ed->second.first, ed->second.second });
			sum += ed->first;
		}
	}
	out << sum << '\n';
	out << picked_edges.size() << '\n';
	for (auto it = picked_edges.begin(); it != picked_edges.end(); it++)
	{
		out << it->first + 1 << ' ' << it->second + 1<< '\n';
	}
}
class Comparator
{
public:
	bool operator()(pair<int, int> a, pair<int, int> b) const
	{
		return a.first > b.first;
	}
};
void Prim(Graph& G)
{
	vector<Edge> dist(G.size(), { -1, INT_MAX });
	priority_queue<pair<int, int>, vector<pair<int, int>>, Comparator> q;
	dist[0] = {-1, 0 };
	int sum = 0;
	vector<bool> added(G.size(), false);
	q.push({ 0, 0 });
	while (!q.empty())
	{
		int node = q.top().second;
		int cost = q.top().first;
		q.pop();
		if (!added[node])
		{
			added[node] = true;
			for (auto it = G[node].begin(); it != G[node].end(); it++)
			{
				if (!added[it->adj_node] && dist[it->adj_node].cost > it->cost)
				{
					dist[it->adj_node].cost = it->cost;
					dist[it->adj_node].adj_node = node;

					q.push({ it->cost, it->adj_node });
				}
			}
		}	
	}
	for (int i = 0; i < dist.size(); i++)
	{
		sum += dist[i].cost;
	}
	out << sum << '\n';
	out << dist.size() - 1 << '\n';
	for (int i = 0; i < dist.size(); i++)
	{
		if (dist[i].adj_node != -1)
			out << i + 1 << ' ' << dist[i].adj_node + 1 << '\n';
	}
}
int main()
{
	int N, M;
	in >> N >> M;
	Graph G(N, vector < Edge>());

	for (int i = 0; i < M; i++)
	{
		int u, v, c;
		in >> u >> v >> c;
		u--; v--;
		G[u].push_back({ v, c });
		G[v].push_back({ u, c });

	}
	Prim(G);
}