#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m, ans, nr;
int tata[200005];
bool M[400005];

struct muchie	 {
	int x, y, c;
} a[400005];

bool cmp(muchie _x, muchie _y)	{
  return (_x.c < _y.c);
}

inline void set_tata(int x, int tx)	{
  int cp;
  while (tata[x] > 0)	 {
		cp = tata[x];
    tata[x] = tx;
    x = cp;
  }
}

inline bool same_tree(int x, int y)	{
  int tx = x, ty = y;
  while (tata[tx] > 0)
		tx = tata[tx];
	while (tata[ty] > 0)
		ty = tata[ty];
  set_tata(y, ty);
  set_tata(x, tx);
  if (tx != ty)
		return false;
	return true;
}

inline void Union(int x, int y)	{
  int tx = x, ty = y;
  while (tata[tx] > 0)
		tx = tata[tx];
  while (tata[ty] > 0)
		ty = tata[ty];
  if (tata[tx] > tata[ty])
		swap(tx, ty), swap(x, y);
	tata[tx] += tata[ty];
	tata[ty] = tx;
  set_tata(x, tx);
  set_tata(y, tx);
}

void afiseaza()	 {
  fout << ans << '\n' << n - 1 << '\n';
  for (int i = 1; i <= m; ++i)
		if (M[i])
			fout << a[i].x << ' ' << a[i].y << '\n';
}

int main()	{
  fin >> n >> m;
  for (int i = 1; i <= m; ++i)
		fin >> a[i].x >> a[i].y >> a[i].c;
  sort (a + 1, a + m + 1, cmp);
  for (int i = 1; i <= n; ++i)
		tata[i] = -1;
  for (int i = 1; i <= m; ++i)	{
    if (same_tree(a[i].x, a[i].y))
			continue;
    Union(a[i].x, a[i].y);
    ans += a[i].c;
    ++nr;
    M[i] = true;
    if (nr == n - 1)	{
			afiseaza();
			return 0;
    }
  }
  return 0;
}