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

int main() {
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	int n, m;
	fin >> n >> m;
	vector<pair<int,int> > adjl[n+1];
	vector<pair<int,int> >::iterator it;
	int u, v, w;
	for (; m > 0; --m) {
		fin >> u >> v >> w;
		adjl[u].push_back(pair<int,int>(v,w));
		adjl[v].push_back(pair<int,int>(u,w));
	}

	int ans = 0;
	vector<int> mst(n+1);
	const int inf = 1<<30;
	vector<int> dist(n+1, inf);
	dist[1] = 0;
	priority_queue<int, vector<pair<int,int> >, greater<pair<int,int> > > pq;
	pq.push(pair<int,int>(0,1));
	while (!pq.empty()) {
		u = pq.top().second;
		w = pq.top().first;
		pq.pop();
		if (w == dist[u]) {
			for (it = adjl[u].begin(); it != adjl[u].end(); ++it) {
				v = it->first; w = it->second;
				if (dist[v] > w) {
					pq.push(pair<int,int>(w,v));
					dist[v] = w;
				}
				if (dist[v] == -inf && w == dist[u]) mst[u] = v;
			}
			ans += dist[u];
			dist[u] = -inf;
		}
	}
	fout << ans << '\n';
	fout << n-1 << '\n';
	for (int i = 2; i <= n; ++i)
		fout << mst[i] << ' ' << i << '\n';
	return 0;
}