// Algoritmul lui Kruskal - O(M log M)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

const int MAX_N = 2e5, MAX_M = 4e5;

struct muchie
{
	int x, y;
	short cost;
} v[MAX_M + 1];

inline bool cmp(muchie a, muchie b)
{
	if (a.cost > b.cost)
		return 0;
	return 1;
}

int t[MAX_N + 1], r[MAX_N + 1];

int Find(int x)
{
	if (t[x] == 0)
		return x;
	return (t[x] = Find(t[x]));
}

void Union(int x, int y)
{
    if (r[x] < r[y])
        t[x] = y;
    else
    {
        t[y] = x;
        if (r[x] == r[y])
            r[x]++;
    }
}

long long costMin;
vector<pair<int, int>> sol;
int n, m;

int main()
{
	f >> n >> m;

	for (int i = 1; i <= m; i++)
		f >> v[i].x >> v[i].y >> v[i].cost;

	sort(v + 1, v + m + 1, cmp);

	for (int i = 1; i <= m; i++)
	{
		int rx = Find(v[i].x);
		int ry = Find(v[i].y);
		if (rx != ry)
		{
			Union(rx, ry);
			sol.push_back({v[i].x, v[i].y});
			costMin += v[i].cost;
		}
	}

	g << costMin << ' ' << n - 1 << '\n';
	for (auto edge : sol)
		g << edge.first << ' ' << edge.second << '\n';

	f.close();
	g.close();
	return 0;
}