#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;
	int d[n + 1], parent[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())
	{
		int v = pq.top().second;
		int v_w = -pq.top().first;
		pq.pop();

		if(d[v] != v_w)
			continue;

		cost += v_w;

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

		for(auto it : adj[v])
		{
			int to = it.first;
			int to_w = it.second;

			if(to_w < d[to])
			{
				d[to] = to_w;
				parent[to] = v;
				pq.push({-d[to], to});
			}
		}
		d[v] = INT_MIN;

	}

	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';
	
	for(int i = 1; i <= n; i ++)
	{
		for(auto it : apm[i])
			if(it.first > i)
				cout<<i<<' '<<it.first<<'\n';
	}

	return 0;
}