#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
FILE *fin=fopen("apm.in","r");
FILE *fout=fopen("apm.out","w");
struct edge
{
	int x,y,cost;
};
struct node
{
	int parent;
	int rg;
};

int comparator(const edge &a,const edge &b)
{
	return (a.cost<b.cost);
}


void show_edges(edge* edges, int n)
{
	for(int i=1;i<=n;i++)
	{
		cout<<edges[i].x<<" "<<edges[i].y<<" "<<edges[i].cost<<endl;
	}
}

void make_set(node* verteces,int i)
{
	verteces[i].parent=i;
	verteces[i].rg=0;
}
int find_p(node* element,int x)
{
	int R=x,y;
	while(R!=element[R].parent)
	{R=element[R].parent;}
	while(x!=element[x].parent)
	{
		y=element[x].parent;
		element[x].parent=R;
		x=y;
	}
	return R;
}
void link(node* element,int x,int y)
{
	if(element[x].rg>element[y].rg)
		element[y].parent=x;
	else
		element[x].parent=y;
	if(element[x].rg==element[y].rg)
		element[y].rg++;
}
void unite(node* element,int x, int y)
{
	link(element,find_p(element,x),find_p(element,y));
}

void kruskal(vector<edge> &apm,edge* edges,int n, int m)
{
	node verteces[n+5];
	for(int i=1;i<=n;i++)
		{make_set(verteces,i);}

	for(int i=1;i<=m;i++)
	{
		if(find_p(verteces,edges[i].x)!=find_p(verteces, edges[i].y))
			{
				apm.push_back(edges[i]);
				unite(verteces, edges[i].x,edges[i].y);
			}
	}

}

int main()
{
	int n,m;
	fscanf(fin,"%d %d",&n,&m);
	edge edges[m+10];
	for(int i=1;i<=m;i++)
	{
		fscanf(fin,"%d %d %d",&edges[i].x,&edges[i].y,&edges[i].cost);
	}
	sort(edges+1,edges+m+1,comparator);
	//show_edges(edges,m);
	vector<edge> apm;
	kruskal(apm,edges,n,m);
	int tot_cost=0;
	for(vector<edge>::iterator it=apm.begin();it!=apm.end();it++)
    {
        tot_cost+=(*it).cost;
    }
    fprintf(fout,"%d \n%d\n",tot_cost,apm.size());
	for(vector<edge>::iterator it=apm.begin();it!=apm.end();it++)
	{
		fprintf(fout,"%d %d \n",(*it).y,(*it).x);
	}
	return 0;
}