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

typedef struct my_struct
{
	int number_of_neighbors;
	int *neighbors;
	int *weights;

}Adjacency_List;

typedef struct my_struct1
{
	int node1;
	int node2;
	int weight;

}Arc; 

int min(int a,int b)
{
	if(a<b)
		return 1;
	return 2;
}

void rebuildTheHeapRemove(Arc **minheap,int index,int arcs_in_heap)
{
		if(2*index>arcs_in_heap)
			return;

		if(2*index+1>arcs_in_heap)
		{
			if((*minheap)[2*index].weight<(*minheap)[index].weight)
			{
				int node1,node2,weight;
				node1=(*minheap)[index*2].node1;
				node2=(*minheap)[index*2].node2;
				weight=(*minheap)[index*2].weight;

				(*minheap)[index*2].node1=(*minheap)[index].node1;
				(*minheap)[index*2].node2=(*minheap)[index].node2;
				(*minheap)[index*2].weight=(*minheap)[index].weight;

				(*minheap)[index].node1=node1;
				(*minheap)[index].node2=node2;
				(*minheap)[index].weight=weight;
			}
		}
		else
		{
			if(min((*minheap)[2*index].weight,(*minheap)[2*index+1].weight)==1 && (*minheap)[index].weight > (*minheap)[2*index].weight )
			{
				int node1,node2,weight;
		
				node1=(*minheap)[index*2].node1;
				node2=(*minheap)[index*2].node2;
				weight=(*minheap)[index*2].weight;

				(*minheap)[index*2].node1=(*minheap)[index].node1;
				(*minheap)[index*2].node2=(*minheap)[index].node2;
				(*minheap)[index*2].weight=(*minheap)[index].weight;

				(*minheap)[index].node1=node1;
				(*minheap)[index].node2=node2;
				(*minheap)[index].weight=weight;


				rebuildTheHeapRemove(minheap,2*index,arcs_in_heap);	
			}
			else if(min((*minheap)[2*index].weight,(*minheap)[2*index+1].weight)==2 && (*minheap)[index].weight > (*minheap)[2*index+1].weight )
			{
				int node1,node2,weight;
		
				node1=(*minheap)[index*2+1].node1;
				node2=(*minheap)[index*2+1].node2;
				weight=(*minheap)[index*2+1].weight;

				(*minheap)[index*2+1].node1=(*minheap)[index].node1;
				(*minheap)[index*2+1].node2=(*minheap)[index].node2;
				(*minheap)[index*2+1].weight=(*minheap)[index].weight;

				(*minheap)[index].node1=node1;
				(*minheap)[index].node2=node2;
				(*minheap)[index].weight=weight;


				rebuildTheHeapRemove(minheap,2*index+1,arcs_in_heap);
			}

		}

}

void rebuildTheHeapAdd(Arc **minheap,int index)
{
	if(index==1)
		return;

	if((*minheap)[index/2].weight>(*minheap)[index].weight)
	{
		int node1,node2,weight;
		
		node1=(*minheap)[index/2].node1;
		node2=(*minheap)[index/2].node2;
		weight=(*minheap)[index/2].weight;


		(*minheap)[index/2].node1=(*minheap)[index].node1;
		(*minheap)[index/2].node2=(*minheap)[index].node2;
		(*minheap)[index/2].weight=(*minheap)[index].weight;

		(*minheap)[index].node1=node1;
		(*minheap)[index].node2=node2;
		(*minheap)[index].weight=weight;


		rebuildTheHeapAdd(minheap,index/2);
	}


}


void pop(Arc **minheap,int *arcs_in_heap)
{
	(*minheap)[1].node1=(*minheap)[*arcs_in_heap].node1;
	(*minheap)[1].node2=(*minheap)[*arcs_in_heap].node2;
	(*minheap)[1].weight=(*minheap)[*arcs_in_heap].weight;
	(*arcs_in_heap)--;

	if((*arcs_in_heap)>1)
		rebuildTheHeapRemove(minheap,1,*arcs_in_heap);

}

void addToHeap(Arc **minheap,int node1,int node2,int weight,int *arcs_in_heap)
{
	(*arcs_in_heap)++;
	
	(*minheap)[*arcs_in_heap].weight=weight;
	(*minheap)[*arcs_in_heap].node1=node1;
	(*minheap)[*arcs_in_heap].node2=node2;

	if(*arcs_in_heap!=1)
		rebuildTheHeapAdd(minheap,*arcs_in_heap);

} 

int main()
{
	FILE *read=fopen("apm.in","r");
	FILE *write=fopen("apm.out","w");

	int number_of_vertices;
	int number_of_arcs;

	fscanf(read,"%d %d",&number_of_vertices,&number_of_arcs);
	
	Adjacency_List* adjlist=calloc(number_of_vertices+1,sizeof(Adjacency_List));	
	Arc * minheap=calloc(number_of_arcs+2,sizeof(Arc));
	int arcs_in_heap=0;
	bool *visited=calloc(number_of_vertices+1,sizeof(bool));
	

	int starting_node=0;
	int node1,node2,weight;

	for(int i=0;i<number_of_arcs;i++)
	{
		fscanf(read,"%d %d %d\n",&node1,&node2,&weight);


		if(starting_node==0)
			starting_node=node1;

		
		if(adjlist[node1].number_of_neighbors==0)
		{
			adjlist[node1].neighbors=calloc(1,sizeof(int));
			adjlist[node1].weights=calloc(1,sizeof(int));

			adjlist[node1].neighbors[0]=node2;
			adjlist[node1].weights[0]=weight;

			adjlist[node1].number_of_neighbors=1;
	
		}
		else
		{
			adjlist[node1].number_of_neighbors++;
		
			adjlist[node1].neighbors=realloc(adjlist[node1].neighbors,adjlist[node1].number_of_neighbors*sizeof(int));
			adjlist[node1].weights=realloc(adjlist[node1].weights,adjlist[node1].number_of_neighbors*sizeof(int));

			adjlist[node1].neighbors[adjlist[node1].number_of_neighbors-1]=node2;
			adjlist[node1].weights[adjlist[node1].number_of_neighbors-1]=weight;

		}
		
		if(adjlist[node2].number_of_neighbors==0)
		{
			adjlist[node2].neighbors=calloc(1,sizeof(int));
			adjlist[node2].weights=calloc(1,sizeof(int));

			adjlist[node2].neighbors[0]=node1;
			adjlist[node2].weights[0]=weight;

			adjlist[node2].number_of_neighbors=1;
	
		}
		else
		{
			adjlist[node2].number_of_neighbors++;
		
			adjlist[node2].neighbors=realloc(adjlist[node2].neighbors,adjlist[node2].number_of_neighbors*sizeof(int));
			adjlist[node2].weights=realloc(adjlist[node2].weights,adjlist[node2].number_of_neighbors*sizeof(int));

			adjlist[node2].neighbors[adjlist[node2].number_of_neighbors-1]=node1;
			adjlist[node2].weights[adjlist[node2].number_of_neighbors-1]=weight;

		}

		
	}

	Arc *MST=calloc(number_of_vertices,sizeof(Arc));


	visited[starting_node]=true;

	for(int i=0;i<adjlist[starting_node].number_of_neighbors;i++)
		addToHeap(&minheap,starting_node,adjlist[starting_node].neighbors[i],adjlist[starting_node].weights[i],&arcs_in_heap); 

	int apmcost=0;
	int number_of_arcs_apm=0;
	
	Arc top;

	while(number_of_arcs_apm<number_of_vertices-1)
	{
		
		top.node1=minheap[1].node1;
		top.node2=minheap[1].node2;
		top.weight=minheap[1].weight;

		pop(&minheap,&arcs_in_heap);

		if(visited[top.node2]==false)
		{

			number_of_arcs_apm++;
			apmcost+=(top).weight;

			MST[number_of_arcs_apm-1].node1=top.node1;
			MST[number_of_arcs_apm-1].node2=top.node2;
			MST[number_of_arcs_apm-1].weight=top.weight;
	
			visited[(top).node2]=true;

			for(int i=0;i<adjlist[(top).node2].number_of_neighbors;i++)
				if(visited[adjlist[(top).node2].neighbors[i]]==false)
					addToHeap(&minheap,(top).node2,adjlist[(top).node2].neighbors[i],adjlist[(top).node2].weights[i],&arcs_in_heap);
		}

	}

	fprintf(write, "%d\n%d\n",apmcost,number_of_arcs_apm);

	for(int i=0;i<number_of_vertices-1;i++)
		fprintf(write,"%d %d\n",MST[i].node1,MST[i].node2);
	
	for(int i=1;i<=number_of_vertices;i++)
		if(adjlist[i].number_of_neighbors!=0)
		{
			free(adjlist[i].neighbors);
			free(adjlist[i].weights);
		}
	
	free(MST);
	free(adjlist);
	free(minheap);
	free(visited);
	fclose(read);
	fclose(write);

	return 0;

}