#include<stdio.h>
#include<vector>
#include<algorithm>
#include<cassert>
#define pb push_back
#define mkp make_pair

using namespace std;

const int maxn = 400000;

int N,M;
int VER[maxn],NR;
int ANS,NOD;
vector<int> VECT[maxn],VECT1[maxn];
vector<pair<int,pair<int,int> > > VECTMU;
vector<pair<int,int> > VANS;

void dfs2(int nod)
{
	if (VER[nod])return;
	VER[nod] = 1;
	for(unsigned int i = 0;i < VECT1[nod].size();++i) dfs2(VECT1[nod][i]);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&N,&M);
	for(int i = 1;i <= M; ++i)
	{
		int x,y,c;
		scanf("%d %d %d",&x,&y,&c);
		VECT[x].pb(y);
		VECT[y].pb(x);
		VECTMU.pb(mkp(c,mkp(x,y)));
	}
	NR = N;
	sort(VECTMU.begin(),VECTMU.end());
	NR = N;
	for(int i = 0;i < M; ++i)
	{
		int cost = VECTMU[i].first;
		int nod1 = VECTMU[i].second.first;
		NOD = VECTMU[i].second.second;
		memset(VER,0,sizeof(VER));
		dfs2(nod1);
		if (!VER[NOD]) {
			--NR;VECT1[nod1].pb(NOD);VECT1[NOD].pb(nod1);ANS += cost;
			VANS.pb(mkp(NOD,nod1));
		}
		if (NR == 1) break;
	}

	printf("%d\n",ANS);
	printf("%d\n",N-1);
	for(int i = 0;i < N - 1; ++i)
		printf("%d %d\n",VANS[i].first,VANS[i].second);
	return 0;
}