#include<stdio.h>
#include<stdlib.h>

#include<set>
#include<list>
#include<queue>

#include <fstream>
#include <iostream>

using namespace std;

#define MAXN 200000
#define MAXM 400000

#define INFINIT 1001
int M,N;
bool ciclu;

list<pair<int,int>> L[MAXN];
set<pair<int,int>> Q; 
queue<pair<int,int>> F;

bool outQ[MAXN];
int C[MAXN];
int E[MAXN];

//ifstream fin("apm.in");
//ofstream fout("apm.out");

int costtotal;

void arboreprim(){
	for(int i=0;i<N;i++){
		Q.insert(make_pair(INFINIT,i));
		C[i]=INFINIT;
		E[i]=-1;
	}

	int nod,vecin,cost;
	set<pair<int,int>>::iterator itS,it; 
	list<pair<int,int>>::iterator itL;

	itS=Q.begin();
	nod=itS->second;
	Q.erase(itS);

	for(itL=L[nod].begin();itL!=L[nod].end();itL++){
		vecin=itL->first;
		cost=itL->second;	
		if(cost<C[vecin]){
			it=Q.find(make_pair(C[vecin],vecin));
			C[vecin]=cost;
			E[vecin]=nod;
			Q.erase(it);
			Q.insert(make_pair(C[vecin],vecin));
		}
	}
	outQ[nod]=1;	

	while(!Q.empty()){
		itS=Q.begin();
		nod=itS->second;
		//if(E[nod]!=-1){			
		// adaugare muchie nod,vecin
		F.push(make_pair(nod,E[nod]));
		costtotal+=C[nod];
	
		Q.erase(itS);

		for(itL=L[nod].begin();itL!=L[nod].end();itL++){
			vecin=itL->first;
			cost=itL->second;	
			if(!outQ[vecin] && cost<C[vecin]){
				it=Q.find(make_pair(C[vecin],vecin));
				C[vecin]=cost;
				E[vecin]=nod;
				Q.erase(it);
				Q.insert(make_pair(C[vecin],vecin));
			}
		}
		outQ[nod]=1;	
	}
}

int main(){
		
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d",&N,&M);
	//fin >> N >> M;

	int x,y,c;

	for(int i=0;i<M;i++){
		scanf("%d %d %d",&x,&y,&c);
		//fin >> x >> y >> c;
		L[x-1].push_back(make_pair(y-1,c));
		L[y-1].push_back(make_pair(x-1,c));
	}

	arboreprim();

	//fout << costtotal << endl;
	//fout << F.size() << endl;
	printf("%d\n",costtotal);
	printf("%d\n",F.size());

	while(!F.empty()){
		x=F.front().first;
		y=F.front().second;
		//fout << x+1 << " " << y+1 << endl;
		printf("%d %d\n",x+1,y+1);
		F.pop();
	}

	//fin.close();
    //fout.close();

	return 0;
}