#include <cstdio>
#include <vector>
#define maxM 524288
#define maxN 200010
using namespace std;

struct heap
{
	int v1, v2, val;
}H[maxM];

vector<int> edge[maxN], cost[maxN];
int n, m, k, nod1[maxN], nod2[maxN], l, total;
short viz[maxN];

void citire()
{
	freopen("apm.in", "r", stdin);
	scanf("%d%d", &n, &m);
	int i, a, b, c;
	for (i=0; i<m; ++i)
	{
		scanf("%d%d%d", &a, &b, &c);
		edge[a].push_back(b);
		edge[b].push_back(a);
		cost[a].push_back(c);
		cost[b].push_back(c);
	}
}

inline void swap(int &a, int &b)
{
	a ^= b;
	b ^= a;
	a ^= b;
}

void sift(int x)
{
	int son;
	do
	{
		son = 0;
		int leftSon = x<<1;
		if (leftSon <= k)
		{
			son = leftSon;
			if (leftSon+1 <= k && H[leftSon+1].val < H[leftSon].val)
				son = leftSon+1;
			if (H[son].val >= H[x].val)
				son = 0;
		}
		if (son)
		{
			swap(H[x].v1, H[son].v1);
			swap(H[x].v2, H[son].v2);
			swap(H[x].val, H[son].val);
			x = son;
		}
	}
	while (son);
}

void percolate(int x)
{
	int key1=H[x].val, key2=H[x].v1, key3=H[x].v2;
	while (x>1 && key1<H[x>>1].val)
	{
		int dad = x>>1;
		H[x].val = H[dad].val;
		H[x].v1 = H[dad].v1;
		H[x].v2 = H[dad].v2;
		x = dad;
	}
	H[x].val = key1;
	H[x].v1 = key2;
	H[x].v2 = key3;
}


void del()
{
	H[1].v1 = H[k].v1;
	H[1].v2 = H[k].v2;
	H[1].val = H[k].val;
	--k;
	sift(1);
}

void Prim()
{
	int v=1, nv=0;
	while (nv < n)
	{
		viz[v] = 1;
		vector<int>::iterator i1=edge[v].begin(), i2=cost[v].begin(), stop=edge[v].end();
		while (i1 != stop)
		{
			H[++k].v1 = v;
			H[k].v2 = *i1;
			H[k].val = *i2;
			percolate(k);
			++i1, ++i2;
		}
		
		//for (int i=k>>1; i>0; --i)
			//sift(i);
		while (viz[H[1].v1] && viz[H[1].v2])
			del();
		
		if (!viz[H[1].v1]) v = H[1].v1;
		else v = H[1].v2;
		viz[v] = 1;
		
		total += H[1].val;
		nod1[++l] = H[1].v1; nod2[l] = H[1].v2;
		del(); ++nv;
	}
}

void afisare()
{
	freopen("apm.out", "w", stdout);
	printf("%d\n%d\n", total, l-1);
	for (int i=1; i<l; ++i)
		printf("%d %d\n", nod1[i], nod2[i]);
}

int main()
{
	citire();
	Prim();
	afisare();
	return 0;
}