#include <bits/stdc++.h>

using namespace std;

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

const int nmx = 2e5 + 5;

int N, M, cost;
vector <pair<int,int>> l[nmx], ans;
bitset <nmx> vis;
set <pair<int,pair<int,int>>> s;

int main() {
	in>>N>>M;

	for(int i = 1; i <= M; ++i) {
		int x, y, c;
		in>>x>>y>>c;
		l[x].push_back({y, c});
		l[y].push_back({x, c});
	}

	vis[1] = 1;

	for(auto k : l[1]) {
		s.insert({k.second, {1, k.first}});
	}

	while(!s.empty()) {
		pair <int,pair<int,int>> fs = *s.begin();
		s.erase(s.begin());
		int from = fs.second.first;
		int to = fs.second.second;
		int cst = fs.first;

		if(vis[to] == 0) {
			vis[to] = 1;
			cost += cst;
			ans.push_back({from, to});
			for(auto k : l[to]) {
				if(vis[k.first] == 0) {
					s.insert({k.second, {to, k.first}});
				}
			}
		}
	}

	out<<cost<<"\n";
	out<<ans.size()<<"\n";
	for(auto k : ans) {
		out<<k.first<<" "<<k.second<<"\n";
	}

	return 0;
}