#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

class edge{
	public :int from,to,cost;
	public: edge(int f,int t,int c):from(f),to(t),cost(c){}
	
	public:bool operator<(const edge& other){return cost<other.cost;}
	public:bool operator>(const edge& other){return cost>other.cost;}
};
int parent[200005];

int getParent(int a){
	if(parent[a]!=a)
		parent[a]=getParent(parent[a]);
	return parent[a];	
}
void unite(int a,int b){parent[getParent(a)]=getParent(b);}
bool isSame(int a,int b){return getParent(a)==getParent(b);}

int main(){

	int f,t,c,n,m;
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	vector<edge> v;
	scanf("%d",&n);scanf("%d",&m);
	
	for(int i=1;i<=n;i++)parent[i]=i;
	
	for(int i=0;i<m;i++){
		scanf("%d",&f);scanf("%d",&t);scanf("%d",&c);
		v.push_back(edge(f,t,c));
	}
	
	sort(v.begin(),v.end());
	
	vector<edge> sol;
	long sum=0;
	for(int i=0;i<v.size();i++){
		if(!isSame(v[i].from,v[i].to)){
			unite(v[i].from,v[i].to);
			sol.push_back(v[i]);
			sum+=v[i].cost;
		}
	}
	printf("%ld\n%d\n",sum,sol.size()); for(int i=0;i<sol.size();i++){printf("%d %d\n",v[i].from,v[i].to);}
	return 0;
}