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

ifstream in("apm.in");
ofstream out("apm.out");


int n,m;
struct edge{
	int origin,destination,cost;
};

struct compare{
	bool operator()(const edge&a,const edge&b){
		return a.cost>b.cost;
	}
};

vector<vector<edge>> graph;
vector<bool> visited;

void read(){
	in>>n>>m;

	int a,b,c;
	graph.resize(n+1);
	visited.resize(n+1);

	for(int i=0;i<m;i++){
		in>>a>>b>>c;
		graph[a].push_back({a,b,c});
		graph[b].push_back({b,a,c});
	}
}

void solve(){
	priority_queue<edge,vector<edge>,compare> edges;	
	visited[1]=true;

	for(edge x:graph[1]){// start with the node 1
		edges.push(x);
	} 

	int total=0;
	vector<edge> result;

	while(!edges.empty()){
		edge here=edges.top();
		edges.pop();
		if(!visited[here.destination]){ // add a new node into the spanning tree.
			visited[here.destination]=true;

			result.push_back(here);
			total+=here.cost;

			for(edge k:graph[here.destination]){ // add its edges to the queue.
				if(!visited[k.destination]){
					edges.push(k);
				}
			}
		}
	}

	out<<total<<'\n';
	out<<result.size()<<'\n';

	for(const edge&e:result){
		out<<e.origin<<" "<<e.destination<<'\n';
	}
}

int main(){
	read();
	solve();
	return 0;
}