#include <cstdio>
#define maxm 400010
#define maxn 200010
using namespace std;

struct nod
{
	int muchie;
	nod *adr;
}*graf[maxn];

struct edge
{
	int v1, v2, cost;
}e[maxm];

int n, m, k, muchii[maxm], total;
int H[1048576];
bool viz[maxn];

void add(int v, int e)
{
	if (graf[v] == NULL)
	{
		graf[v] = new nod;
		graf[v]->muchie = e;
		graf[v]->adr = NULL;
		return;
	}
	
	nod *p = new nod;
	p->muchie = e;
	p->adr = graf[v];
	graf[v] = p;
}

void citire()
{
	freopen("apm.in", "r", stdin);
	scanf("%d%d", &n, &m);
	int i, a, b, c;
	for (i=1; i<=m; ++i)
	{
		scanf("%d%d%d", &a, &b, &c);
		e[i].v1=a; e[i].v2=b; e[i].cost=c;
		//H[i] = i;
		add(a, i); add(b, i);
	}
	k = --i;
}

int father(int k)
{
	return k/2;
}

int leftSon(int k)
{
	return 2*k;
}

int rightSon(int k)
{
	return 2*k + 1;
}

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

void sift(int n, int k)
{
	int son;
	do
	{
		son = 0;
		if (leftSon(k) <= n)
		{
			son = leftSon(k);
			if (rightSon(k) <= n)
				if (e[H[leftSon(k)]].cost > e[H[rightSon(k)]].cost)//if (H[leftSon(k)] < H[rightSon(k)])
					son = rightSon(k);
			if (e[H[son]].cost >= e[H[k]].cost)//if (H[son] <= H[k])
				son = 0;
		}
		
		if (son)
		{
			swap(H[k], H[son]);
			k = son;
		}
	}
	while (son);
}

void percolate(int N, int K) 
{
    int key = H[K];
    while ((K > 1) && (e[key].cost < e[H[father(K)]].cost)) 
	{
        H[K] = H[father(K)];
        K = father(K);
    }
    H[K] = key;
}

void insert(int &N, int key) 
{
    H[++N] = key;
    percolate(N, N);
}

void cut(int &N, int K) 
{
    H[K] = H[N];
    --N;
 
    if ((K > 1) && (e[H[K]].cost < e[H[father(K)]].cost)) 
        percolate(N, K);
    else
        sift(N, K);
}

void Prim()
{
	int v, j, i=0, nrv=1;
	viz[1] = 1;
	
	nod *p = graf[1];
	while (p)
	{
		H[++i] = p->muchie;
		p = p->adr;
	}
	
	for (j=i>>1; j>0; --j)
		sift(i, j);
	muchii[++k] = H[1];
	total += e[H[1]].cost;
	if (viz[e[H[1]].v1])
		v = e[H[1]].v2;
	else v = e[H[1]].v1;
	cut(i, 1);
	
	while (nrv < n)
	{
		p = graf[v];
		viz[v] = 1;
		++nrv;
		
		while (p)
		{
			insert(i, p->muchie);
			p = p->adr;
		}
		
		muchii[++k] = H[1];
		total += e[H[1]].cost;
		if (viz[e[H[v]].v1])
			v = e[H[v]].v2;
		else v = e[H[v]].v1;
		cut(i, 1);
	}
}

void afisare()
{
	freopen("apm.out", "w", stdout);
	printf("%d\n%d\n", total, k);
	for (int i=1; i<=k; ++i)
		printf("%d %d\n", e[muchii[i]].v1, e[muchii[i]].v2);
}

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