#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "apm.in"
#define outfile "apm.out"
#define n_max 200005
#define INF 1<<30
#define pb push_back
#define mkp make_pair
#define min(x,y) x<y ? x : y
#define ls(i) i<<1
#define rs(i) (i<<1) + 1
#define f(i) i>>1
using namespace std;


vector < pair < int, int> > v[n_max], apm; //v - graful, apm - apm-ul obtinut

int H[n_max], cmin[n_max], poz[n_max], t[n_max] ;//H - heap, cmin[i] = muchia de cost minim catre i, poz[i] = pozitia lui i in heap,  t[i] = tatal lui i

int n, m, cost_apm, N;


void percolate(int);
void introduce_in_heap(int);


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&n,&m);
	
	int x,y,c;
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d", &x, &y, &c);
		
		v[x].pb( mkp(y,c) );
		v[y].pb( mkp(x,c) );
	}
	
	fclose(stdin);
}


void introduce_in_apm (int x)
{
	for(unsigned int i=0; i<v[x].size();++i)
	{
		int nod = v[x][i].first;
		int cost = v[x][i].second;
		
		cmin[nod] = min(cmin[nod], cost);
		
		if(cmin[nod] == cost)
			t[nod] = x;
	}
}



void init()
{
	for(int i=2;i<=n;i++)
		cmin[i] = INF;
	
	introduce_in_apm(1);
	
	for(int i = 2;i <= n; ++i)
		introduce_in_heap(i);
}



void introduce_in_heap(int nod)
{
	H[++N] = nod;
	
	poz[nod] = N;
	
	percolate(N);
}


void sift(int k)
{
	int son = k, l = ls(k), r = rs(k);
	
	if(l<=N && cmin[H[l]] < cmin[H[son]])
		son = l;
	if(r<=N && cmin[H[r]] < cmin[H[son]])
		son = r;
	
	if(son!=k)
	{
		swap(poz[H[son]], poz[H[k]]);
		swap(H[son], H[k]);
		
		sift(son);
	}
}



void percolate(int k)
{
	while(k > 1 && cmin[H[k]] < cmin[H[f(k)]] )
	{
		swap(poz[H[k]], poz[H[f(k)]] );
	    swap(H[k], H[f(k)]);
		
		k = f(k);
	}
}


int vf_heap()
{
	int x = H[1];
	
	poz[x] = 0;
	
	H[1] = H[N--];
	
	poz[H[1]] = 1;
	
	sift(1);
	
	return x;
}
	



void rezolva()
{
	
	for(int i=1;i<n;i++)
	{
		int x = vf_heap();
		
		introduce_in_apm(x);
		
		cost_apm += cmin[x];
		
		apm.pb( mkp(x,t[x]) );
		
		for(unsigned int i=0; i<v[x].size(); ++i)
		{
			int nod = v[x][i].first;
			
			if(poz[nod])
				percolate(poz[nod]);
		}
	}
}



void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",cost_apm);
	
	printf("%d\n",n-1);
	
	for(int i=0;i<n-1;i++)
		printf("%d %d\n",apm[i].first, apm[i].second);
	
	fclose(stdout);
}

int main()
{
	citeste();
	init();
	rezolva();
	afiseaza();
	
	return 0;
}