#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

#define maxn 200001
#define maxm 400001

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

vector <int> vecini[maxn] ;
vector <int> cost[maxn] ;
int n,m ;
muchii mc[maxm] ;
muchii sol[maxm] ;
int sel[maxn] ;
int num ;
int tata[maxn] ;

bool cmp(muchii a,muchii b)
{
	return a.c < b.c ;
}

int rezolvare(int x)
{
	if( tata[x] == x )
		return x;
	tata[x] = rezolvare(tata[x]);
	return tata[x];
}

bool drum(int x,int y)
{
	rezolvare ( x ) ;
	rezolvare ( y ) ;
	return ( tata[y] == tata[x] ) ;
}

int main()
{
	
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for( int i = 1; i<= n; ++i)
		tata[i] = i;
	for(int i=1;i<=m;++i)
	{
		int a,b,c ;
		scanf("%d%d%d",&a,&b,&c);
		mc[i].x = a ;
		mc[i].y = b ;
		mc[i].c = c ;
	}

	sort(mc+1,mc+m+1,cmp) ;

	int solcost = 0 ;
	for(int i=1;i<=m;++i)
	{
		
		if( drum ( mc[i].x , mc[i].y ) == false )
		{
			++ num ;
			solcost += mc[i].c ;
			sol[num].x = mc[i].x ;
			sol[num].y = mc[i].y ;
			tata[tata[sol[num].x]] = tata[sol[num].y] ;
		}
		memset(sel,0,sizeof(sel)) ;
		
	}

	printf("%d\n%d\n",solcost,num);
	for(int i=1;i<=num;++i)
		printf("%d %d\n",sol[i].x,sol[i].y);
	
	return 0;
	
}