//#include "Pch.h"
#include <fstream>
#include <algorithm>
#define NMAX 400001
using namespace std;

int height[NMAX], father[NMAX];

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


struct muchie
{
	int x, y, c;
};

void MakeSet(int x)
{
	if (father[x] == 0 && height[x] == 0)
	{
		father[x] = x;
		height[x] = 1;
	}
}

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

int FindSet(int x)
{
	if (father[x] != x)
		father[x] = FindSet(father[x]);

	return father[x];
}

void citire(int *n, int *m, muchie v[])
{
	f >> *n >> *m;
	for (int i = 1; i <= *m; ++i)
		f >> v[i].x >> v[i].y >> v[i].c;
}

inline bool comp(muchie a, muchie b)
{
	return a.c < b.c;
}


void afisare(int cost, int sol[], muchie v[], int k, int n)
{
	g << cost << '\n' << n - 1 << '\n';

	for (int i = 0; i < k; ++i)
		g << v[sol[i]].x << " " << v[sol[i]].y << '\n';
}


int main()
{
	muchie v[NMAX];
	int sol[NMAX];
	int n, m, k=0, cost=0;

	citire(&n, &m, v);

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

	int a, b;
	for (int i = 1; i <= m && k < n; ++i)
	{
		a = v[i].x;
		b = v[i].y;

		MakeSet(a);
		MakeSet(b);

		a = FindSet(a);
		b = FindSet(b);

		if (a != b)
		{
			sol[k++] = i;
			cost += v[i].c;
			Union(a, b);
		}
	}
	afisare(cost, sol, v, k, n);
	return 0;
}