#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 ;

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

void df(int nod)
{
	sel[nod] = 1 ;
	for(size_t i=0;i<vecini[nod].size();++i)
	{	
		int nod_act = vecini[nod][i] ;
		if( sel[nod_act] == 0 )
			df ( nod_act ) ;
	}	
}

bool drum(int x,int y)
{
	df ( x ) ;
	return ( sel[y] == 1 ) ;
}

int main()
{
	
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	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 ;
			sol[num].c = mc[i].c ;
			vecini[sol[num].x].push_back(sol[num].y) ;
			vecini[sol[num].y].push_back(sol[num].x) ;
			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;
	
}