#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define inf 100000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int main()
{
	int n, m;
	f >> n >> m;
	vector <vector <pair <int, int> > > Graph(n+1);
	vector <int> viz(n + 1, 0), d(n + 1, inf), t(n + 1, 0);
	set <pair <int, int> > S;
	for (int i = 1; i <= m; i++)
    {
		int x, y, cost;
		f >> x >> y >> cost;
		Graph[x].push_back({ cost,y });
		Graph[y].push_back({ cost,x });
	}
	S.insert({ 0,1 });
	d[1] = 0;
	while (!S.empty())
    {
		int nod = S.begin()->second;
		viz[nod] = 1;
		S.erase(S.begin());
		for (auto i : Graph[nod])
		{
			if (viz[i.second] == 0 && i.first < d[i.second])
			{
				d[i.second] = i.first;
				S.insert({d[i.second], i.second});
				t[i.second] = nod;
			}
		}
	}
	int cost = 0;
	for (int i = 1; i <= n; i++)
    {
		cost += d[i];
	}
	g << cost << '\n' << n - 1 << '\n';
	for (int i = 2; i <= n; i++)
    {
		g << i << ' ' << t[i]<< '\n';
	}
    return 0;
}