#include<stdio.h>
#include<algorithm>
#include <queue>
#include<vector>
#define pb push_back

using namespace std;

const int maxn = 400100;

int GR[maxn],X[maxn],Y[maxn],C[maxn];
int N,M,ANS;
vector<int> VANS;

struct cmpf
{
  bool operator() (int i,int j) 
  {
    return(C[i] > C[j]);;
  }
};
  

priority_queue <int,vector<int>,cmpf> IND;

int grupa(int i)
{
	if (GR[i] == i) return i;
	GR[i] = grupa(GR[i]);
	return GR[i];
}

void reuniune(int i,int j)
{
	GR[grupa(i)] = grupa(j); 
}

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)
	{
		scanf("%d %d %d\n",&X[i],&Y[i],&C[i]);
		IND.push (i);
	}

	for(int i = 1;i <= N; ++i) GR[i] = i;
  int ind;
	while (VANS.size () !=N-1)
	{
    ind=IND.top(); IND.pop();
		if (grupa(X[ind]) != grupa(Y[ind])){
			ANS += C[ind];reuniune(X[ind],Y[ind]);
			VANS.pb(ind);
		}
	}
	printf("%d\n",ANS);
	printf("%d\n",N - 1);
	for(int i = 0;i < N - 1; ++i)
		printf("%d %d\n",X[VANS[i]],Y[VANS[i]]);
	return 0;
}