#include<stdio.h>
#include<queue>
#include<utility>
#include<algorithm>
#include<vector>

using namespace std;

FILE *in,*out;

//definitions
#define type pair<int,pair<int,int> >
#define cost first
#define from second.first 
#define to second.second
#define mp make_pair
#define pii pair<int, int>
#define pb push_back


//constants
const int sz = (int) 2e5+1;

//variables
int nodes, edges;
int node1, node2, weight;

priority_queue< type, vector<type>, greater<type> > q;

int finalCost;

vector<pii> answer;

int tata[sz];

//functions
int getRoot(int node);

int main(void)
{
	in = fopen("apm.in", "rt");
	out = fopen("apm.out", "wt");
	
	fscanf(in, "%d%d", &nodes, &edges);
	
	while(edges--)
	{
		fscanf(in, "%d%d%d", &node1, &node2, &weight);
		q.push(mp(weight,mp(node1,node2)));		
	}
	
	while(!q.empty())
	{
		pair<int, pair<int, int> > current = q.top();
		q.pop();
		
		int w = getRoot(current.from);
		int q = getRoot(current.to);
		
		if(w!=q)
		{
			tata[q] = w;
			finalCost += current.cost;
			answer.pb(mp(current.from,current.to));
			
		}
	}
	
	fprintf(out, "%d\n", finalCost);
	
	fprintf(out, "%d\n", answer.size());
	vector<pii> :: iterator it, end=answer.end();
	for( it=answer.begin(); it!=end; ++it)
		fprintf(out,"%d %d\n", it->first, it->second);
	
	fclose(in);
	fclose(out);
	return 0;
}

int getRoot(int node)
{
	if(tata[node])
	{
		tata[node] = getRoot(tata[node]);
		return tata[node];
	}
	return node;
}