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

#define maxn 50001
#define INF 1000000000

vector <int> vecini[maxn] ;
vector <int> cost[maxn] ;
vector <int> muchii[maxn] ;
int n,m ;
int sel[maxn] ;
int nr ;
int num ;
int sol ;
int val ;

void rezolvare(int nod)
{
	
	if( nr == n - 1 )
		return ;
	
	sel[nod] = 1 ;
	++ nr ;
	
	int nod_min ;
	val = INF ;
	for(size_t i=0;i<vecini[nod].size();++i)
	{
		int nod_act = vecini[nod][i] ;
		if( cost[nod][i] < val && sel[nod_act] == 0 )
		{
			nod_min = nod_act ;
			val = cost[nod][i] ;
		}	
	}
	
	if( nod < nod_min )
		muchii[nod].push_back(nod_min) ;
	else
		muchii[nod_min].push_back(nod) ;
	sol += val ;
	rezolvare ( nod_min ) ;
	
}

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);
		vecini[a].push_back(b) ;
		vecini[b].push_back(a) ;
		cost[a].push_back(c) ;
		cost[b].push_back(c) ;
	}	
	
	rezolvare(1) ;
	
	int num = n - 1 ;
	
	printf("%d\n%d\n",sol,num);
	
	for(int i=1;i<=n;++i)
		for(size_t j=0;j<muchii[i].size();++j)
			printf("%d %d\n",i,muchii[i][j]);
	
	return 0;
	
}