#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define cin f
#define cout g
const int Max = 1e5 + 1;

struct Edge
{
	int u, v, weight;
	bool operator<(const Edge &ob)
	{
		return weight < ob.weight;
	}
};

class Kruskal
{
public:
	vector<int> parent, rank;

	void make_set(int x)
	{
		parent[x] = x;
		rank[x] = 0;
	}

	int find_set(int x)
	{
		if(x == parent[x])
			return x;
		return parent[x] = find_set(parent[x]);
	}

	void union_sets(int x, int y)
	{
		x = find_set(x);
		y = find_set(y);

		if(x != y)
		{
			if(rank[x] < rank[y])
				swap(x, y);
			parent[x] = y;
			if(rank[x] == rank[y])
				rank[x] ++;
		}
	}

	void kruskal(int n, vector<pair<int, int>> adj[], vector<pair<int, int>> apm[], int &cost) 
	{
		cost = 0;
		vector<Edge> edges, result;

		parent.resize(n + 1);
		rank.resize(n + 1);

		for(int i = 1; i <= n; i ++)
		{
			make_set(i);
			for(auto it : adj[i])
			{
				if(it.first > i)
					edges.push_back({i, it.first, it.second});
			}
		}

		sort(edges.begin(), edges.end());

		for(Edge e : edges)
		{
			if(find_set(e.u) != find_set(e.v))
			{
				cost += e.weight;
				result.push_back(e);
				union_sets(e.u, e.v);
			}

			if(result.size() == n - 1)
				break;
		}

		for(Edge e : result)
		{
			apm[e.u].push_back({e.v, e.weight});
			apm[e.v].push_back({e.u, e.weight});
		}
	}

	void remove()
	{
		parent.clear();
		rank.clear();
	}
};

int n, m;
vector<pair<int, int>> adj[Max], apm[Max];

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		adj[x].push_back(make_pair(y, w));
		adj[y].push_back(make_pair(x, w));
	}

	int cost, edges;
	Kruskal kr;
	kr.kruskal(n, adj, apm, cost);
	kr.remove();

	cout<<cost<<'\n';

	edges = 0;
	for(int i = 1; i <= n; i ++)
		edges += apm[i].size();
	edges /= 2;
	cout<<edges<<'\n';
	
	for(int i = 1; i <= n; i ++)
	{
		for(auto it : apm[i])
			if(it.first > i)
				cout<<i<<' '<<it.first<<'\n';
	}

	return 0;
}