#include <fstream>
#include <vector>
using namespace std;

#define maxn 200001
#define maxm 400001

typedef struct muchie{
	int x,y,cost;};

int t[maxn],n,m,nh;
vector <pair<int,int> > a[maxn];
muchie b[maxm];

void swap(int x,int y){
	muchie aux;
	aux=b[x];
	b[x]=b[y];
	b[y]=aux;}

void sift(int k){
	int son;
	do{
		son=0;
		if(k*2<=nh)
			son=k*2;
		if(k*2+1<=nh&&b[k*2].cost>b[k*2+1].cost)
			son=k*2+1;
		if(b[son].cost>b[k].cost)
			son=0;
		if(son){
			swap(son,k);
			k=son;}}
	while(son);}

void push(int k){
	while(k/2&&b[k].cost<b[k/2].cost){
		swap(k,k/2);
		k=k/2;}}

void pop(){
	swap(1,nh);
	nh--;
	sift(1);}

int root(int k){
	while(t[k]!=k)
		k=t[k];
	return k;}

void add(int nod){
	muchie k;
	for(int i=0;i<a[nod].size();i++){
		k.x=nod;
		k.y=a[nod][i].first;
		k.cost=a[nod][i].second;
		nh++;
		b[nh]=k;
		push(nh);}}

int main(){
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	int nod,i,x,y,z,c=0;
	muchie min;
	for(i=1;i<=m;i++){
		f>>x>>y>>z;
		a[x].push_back(make_pair(y,z));
		a[y].push_back(make_pair(x,z));}
	t[1]=1;
	add(1);
	while(nh){
		min=b[1];
		pop();
		if(root(min.x)!=root(min.y)){
			c=c+min.cost;
			if(root(min.x)==1){
				t[min.y]=min.x;
				nod=min.y;}
			else {
				t[min.x]=min.y;
				nod=min.x;}
			add(nod);}}
	g<<c<<"\n"<<n-1<<"\n";
	for(i=2;i<=n;i++)
		g<<i<<" "<<t[i]<<"\n";
	f.close();
	g.close();
	return 0;}