#include <fstream>
#include <set>
#include <vector>

using namespace std;

vector <pair<int, int > > mst[200005], e[200005];

int color[200005];

struct edge
{
	int x, y, cost;
}medge[400005];

void dfs(int x, int col)
{
	if(color[x]!=0)
		return;
	color[x]=col;

	for(auto ed : mst[x])
	{
		int node=ed.first;
		dfs(node, col);
	}

}

int main()
{
	ifstream cin("apm.in");
	ofstream cout("apm.out");

	int n, m, a, b, c, costt=0, col;
	set <pair<int, int > > add;
	cin>>n>>m;

	for(int i=0;i<m;i++)
	{
		cin>>a>>b>>c;
		e[a].push_back({b, c});
		e[b].push_back({a, c});
	}

	for(int k=0;k<50;k++)
	{
		for(int i=1;i<=n;i++)
			color[i]=0;

		col=0;
		for(int i=1;i<=n;i++)
		{
      if(color[i]==0)
			{
				col++;
				dfs(i, col);
			}
		}

		for(int i=1;i<=col;i++)
		{
			medge[i].x=-1;
			medge[i].y=-1;
			medge[i].cost=1024*1024*1024+7;
		}

		for(int i=1;i<=n;i++)
		{
			for(auto ed : e[i])
			{
				int co=color[i];
				if(ed.second<medge[co].cost && color[ed.first]!=color[i])
				{
          medge[co].x=i;
          medge[co].y=ed.first;
          medge[co].cost=ed.second;
				}
			}
		}

		for(int i=1;i<col;i++)
		{
			pair <int, int> gugu;

			edge ed = medge[i];

			gugu={min(ed.x, ed.y), max(ed.x, ed.y)};

			if(add.count(gugu)>0)
				continue;

			add.insert(gugu);
			mst[ed.x].push_back({ed.y, ed.cost});
			mst[ed.y].push_back({ed.x, ed.cost});

			costt+=ed.cost;
		}
	}

	cout<<costt<<'\n'<<n-1<<'\n';
	for(auto ed : add)
	{
		cout<<ed.first<<" "<<ed.second<<'\n';
	}

	return 0;
}