#include <bits/stdc++.h>
#define ll long long 
#define mp make_pair
#define pb push_back
#define st first
#define nd second 
#define pq priority_queue

using namespace std;

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

int a, b, n, m, cost, ans; bool viz[200200];
vector < pair <int, int> > v[200200], sol;
set < pair <int, pair <int, int> > > heap;

int main(){
	in >> n >> m;
	for(int i = 1; i <= m; i++){
		in >> a >> b >> cost;
		v[a].pb(mp(b, cost));
		v[b].pb(mp(a, cost));
	}
	
	heap.insert(mp(0, mp(0, 1)));
	pair <int, pair <int, int> > help;
	
	while(!heap.empty()){
		
		help = *heap.begin();
		int father = help.nd.st; 
		int son = help.nd.nd;
		heap.erase(heap.begin());
		
		if(!viz[son]){
				
			viz[son] = 1;	 	
			ans += help.st;
			sol.pb(mp(father, son));
			
			for(auto it : v[son])
				if(!viz[it.st])
					heap.insert(mp(it.nd, mp(son, it.st)));
		
		}
	}
	
	out << ans << '\n' << sol.size()-1 << '\n';
	for(auto it = sol.begin()+1; it != sol.end(); ++it)
		out << it->st << ' ' << it->nd << '\n';
			
	return 0;
}