#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;

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

int prim()
{
	int cost = 0, edges = 0;
	int d[n + 1], parent[n + 1];
	bool selected[n + 1] = {};
	priority_queue<pair<int, int>> pq;

	for(int i = 1; i <= n; i ++)
	{
		d[i] = INT_MAX;
		parent[i] = -1;
	}
	d[1] = 0;
	pq.push({0, 1});

	while(! pq.empty())
	{
		pair<int, int> temp = pq.top();
		pq.pop();
		int v = temp.second, w = -temp.first;

		selected[v] = true;
		cost += w;

		if(parent[v] != -1)
		{
			apm[v].push_back({parent[v], w});
			apm[parent[v]].push_back({v, w});
			edges ++;

			if(edges == n - 1)
				break;
		}

		for(auto it : adj[v])
		{
			if(! selected[it.first] and it.second < d[it.first])
			{
				d[it.first] = it.second;
				parent[it.first] = v;
				pq.push({-it.second, it.first});
			}
		}

		while(selected[pq.top().second])
			pq.pop();
	}

	return cost;
}

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 = prim();

	cout<<cost<<'\n'<<n - 1<<'\n';
	
	int ans = 0;
	for(int i = 1; i <= n; i ++)
	{
		for(auto it : apm[i])
			if(it.first > i)
				cout<<i<<' '<<it.first<<'\n';
	}

	return 0;
}