#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;

#define NMAX 200001
#define MMAX 400001

struct muchie {
	int x,y,cost;
	muchie (int _x, int _y, int _cost) {
		x=_x;
		y=_y;
		cost=_cost;
	}
};

vector <muchie> v[NMAX],T[NMAX],e;
int viz[NMAX],c[NMAX],p[NMAX];

void builtT(int nod)
{
	viz[nod]=1;
	for(vector <muchie> :: iterator it=v[nod].begin();it!=v[nod].end();it++) 
		if(viz[it->y]==0) {
			T[nod].push_back(muchie(it->x,it->y,it->cost));
			T[it->y].push_back(muchie(it->y,it->x,it->cost));
			builtT(it->y);
		}
}

void sterge(int x, int y)
{
	for(vector <muchie> :: iterator it=T[x].begin();it!=T[x].end();it++)
		if(it->y==y) {
			T[x].erase(it);
			return ;
		}
}

int cauta(int x, int y)
{
	for(vector <muchie> :: iterator it=T[x].begin();it!=T[x].end();it++)
		if(it->y==y) 
			return 1;
	return 0;
}
int add_edge(int nr)
{
	int u,vv,cost,x,y,max,st,dr,nod;
	u=e[nr].x;
	vv=e[nr].y;
	cost=e[nr].cost;
	memset(viz,0,sizeof(viz));
	memset(p,0,sizeof(p));
	st=1;
	dr=1;
	c[st]=u;
	viz[u]=1;
	while(st<=dr) {
		nod=c[st];
		st++;
		if(viz[vv]==1)
			break;
		for(vector <muchie> :: iterator it=T[nod].begin();it!=T[nod].end();it++)
			if(viz[it->y]==0) {
				c[++dr]=it->y;
				viz[it->y]=1;
				p[it->y]=nod;
				if(it->y==vv)
					break;
			}
	}
	max=-(1<<30);
	for(nod=vv;nod!=0;nod=p[nod]) 
		for(vector <muchie> :: iterator it=T[nod].begin();it!=T[nod].end();it++) {
			if(it->y==p[nod]) {
				if(it->cost>max) {
					max=it->cost;
					x=nod;
					y=p[nod];
				}
				break;
			}
		}
	if(max<=cost)
		return 0;
	e[nr].x=x;
	e[nr].y=y;
	e[nr].cost=max;
	sterge(x,y);
	sterge(y,x);
	T[u].push_back(muchie(u,vv,cost));
	T[vv].push_back(muchie(vv,u,cost));
	return 1;
}

int main ()
{
	int n,m,x,y,cost,i,cmin;
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		v[x].push_back(muchie(x,y,cost));
		v[y].push_back(muchie(y,x,cost));
	}
	f.close();
	builtT(1);
	for(i=1;i<=n;i++)
		for(vector <muchie> :: iterator it=v[i].begin();it!=v[i].end();it++)
			if(cauta(i,it->y)==0 && i<it->y) 
				e.push_back(muchie(i,it->y,it->cost));
	m=e.size()-1;
	for(i=0;i<=m;i++) 
		if(add_edge(i)==1)
			i=-1;
	cmin=0;
	for(i=1;i<=n;i++)
		for(vector <muchie> :: iterator it=T[i].begin();it!=T[i].end();it++)
			if(i<it->y)
				cmin=cmin+it->cost;
	g<<cmin<<'\n'<<n-1<<'\n';
	for(i=1;i<=n;i++)
		for(vector <muchie> :: iterator it=T[i].begin();it!=T[i].end();it++)
			if(i<it->y)
				g<<i<<" "<<it->y<<'\n';
	g.close();
	return 0;
}