#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int DIM = 2e5 + 1;

vector <pair <int, int> > adj[DIM];
bitset <DIM> vis;

struct Edge
{
	int x, y, c;
	
	Edge(int x, int y, int c) : x(x), y(y), c(c) {}
};

struct cmp
{
	bool operator() (Edge a, Edge b)
	{
		return a.c > b.c;
	}
};

main()
{
	int n, m;
	fin >> n >> m;
	
	for(; m; --m)
	{
		int x, y, c;
		fin >> x >> y >> c;
		
		adj[x].emplace_back(y, c);
		adj[y].emplace_back(x, c);
	}
	
	priority_queue <Edge, vector <Edge>, cmp> pq;
	
	vis[1] = true;
	
	for(auto i : adj[1])
		pq.emplace(Edge(1, i.first, i.second));
	
	vector <pair <int, int> > ans;
	int sum = 0;
	
	while(!pq.empty())
	{
		int x = pq.top().x;
		int y = pq.top().y;
		int c = pq.top().c;
		
		pq.pop();
		
		if(vis[y])
			continue;
		
		sum += c;
		ans.emplace_back(x, y);
		vis[y] = true;
		
		for(auto i : adj[y])
			if(!vis[i.first])
				pq.emplace(Edge(y, i.first, i.second));
	}
	
	fout << sum << '\n';
	fout << ans.size() << '\n';
	
	for(auto i : ans)
		fout << i.first << ' ' << i.second << '\n';
}