#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#define MMAX 400000
#define NMAX 200000

using namespace std;

int N,M,x,y,c,*tata,*rang,card,cost,nod;
struct Vect
{
	int x,y,c;
} *Edge;
vector<int> *V,APM,paduri[NMAX];
queue<int> Q;


int get_father(int i)
{
	int x,z;;
	for(x = i ; x!=tata[x]; x=tata[x]);
	for( ; i != tata[i] ; ) 
	{		
		z = tata[i];
		tata[i] = x;
		i = z;
	}
	return x;
}

void unite(int x,int y)
{
	if(rang[x]>rang[y]) tata[y] = x;
	else tata[x] = y;
	if(rang[x] == rang[y]) rang[y]++;
}

int comp(int a , int b)
{
	return Edge[a].c > Edge[b].c;
}


int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d",&N,&M);
	tata = new int[N+2];
	rang = new int[N+2];
	Edge = new Vect[M+5];
	V = new vector<int>[N+2];
	for(int i = 1 ;i <= M ;i++)
	{
		
		scanf("%d %d %d",&x,&y,&c);
		V[x].push_back(i);
		V[y].push_back(i);
		Edge[i].x = x;
		Edge[i].y = y;
		Edge[i].c = c;
	}
	Edge[M+1].c = 2000000;
	for(int i = 1 ; i <= N ; i++)
	{
		rang[i] = 1 ;
		paduri[i].push_back(i);
		tata[i] = i;
		Q.push(i);
		make_heap(V[i].begin(),V[i].end(),comp);
	
	}
    card = 0;
	while(card < N-1 )
	{
		if(Q.empty()) break;
		nod = Q.front();
		Q.pop();
		if(paduri[nod].empty()) continue; 
		int e,tx,ty,minim,piv;
		e = M+1;
		piv = M+1;
		vector<int>::iterator it;
		for(it = paduri[nod].begin();it!=paduri[nod].end();it++)
			if(!V[*it].empty() && Edge[e].c > Edge[V[*it].front()].c) {e = V[*it].front();piv = *it;}
		
		if(piv == M+1 )continue;
		pop_heap(V[piv].begin(),V[piv].end(),comp);
		V[piv].pop_back(); 
		tx = get_father(Edge[e].x);
		ty = get_father(Edge[e].y);
		if(tx!=ty)
		{
			cost+=Edge[e].c;
			APM.push_back(e);
			card++;
			int setNum = rang[tx] + rang[ty];
            if (rang[tx] > rang[ty]) {
                    tata[tx] = ty;
					while(!paduri[tx].empty())
					{
						paduri[ty].push_back(paduri[tx].back());
						paduri[tx].pop_back();
					}
                    Q.push(ty);
            } else {
                    tata[ty] = tx;
					if(rang[tx] == rang[ty] ) rang[ty]++; 
                    paduri[tx].push_back(ty);
					while(!paduri[ty].empty())
					{
						paduri[tx].push_back(paduri[ty].back());
						paduri[ty].pop_back();
					}
					Q.push(tx);
			}
		}
		else Q.push(tx);
	}
	printf("%d\n%d\n",cost,N-1);
	vector<int>::iterator it;
	for(it=APM.begin();it!=APM.end();it++)
		printf("%d %d\n",Edge[*it].x,Edge[*it].y);
	return 0;

}