#include <cstdio>
#include <queue>

using namespace std;

int n,m,viz[100005];
int muchii = 0, costG = 0;

vector<pair<int, int> >Graph[100005];
vector<pair<int, int> >apm;

priority_queue<pair <int, pair<int, int> > > myHeap;


void Read(){
	int aux1, aux2, cost;
	FILE *f = fopen("apm.in","r");
	fscanf(f,"%d %d",&n,&m);
	for(int i=0;i<m;i++){
		fscanf(f,"%d %d %d",&aux1,&aux2,&cost);
		Graph[aux1].push_back(make_pair(aux2, cost));
		Graph[aux2].push_back(make_pair(aux1, cost));
	}
	fclose(f);
}

void Prim(int start){
	viz[start] = 1;

	for(int i=0;i<Graph[start].size();i++){
		myHeap.push(make_pair(-Graph[start][i].second, make_pair(start, Graph[start][i].first)));
	}

	while(!myHeap.empty()){
		pair<int,pair<int,int> > best = myHeap.top();
		myHeap.pop();
		int index = best.second.second;
		if(viz[index])
			continue;
		viz[index] = 1;
		muchii ++;
		costG = costG - best.first; //Face + , - cu -
		apm.push_back(best.second);
		for(int i=0;i<Graph[index].size();i++){
			int vecin = Graph[index][i].first;
			int cost = Graph[index][i].second;
			myHeap.push(make_pair(-cost, make_pair(index, vecin)));
		}

	}
}

int main(){
	FILE *g = fopen("apm.out","w");
	Read();
	Prim(1);
	fprintf(g,"%d\n%d\n",costG, muchii);
	for(int i=0;i<muchii;i++)
		fprintf(g,"%d %d\n",apm[i].first, apm[i].second);
	return 0;
}