#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
using pii = pair<int,int>;
const int inf = 1e9+7;
const int lim = 2e5+4;
int dist[lim];
int unde[lim];
bool included[lim];
vector<pii> vec[lim];
set<pii> s;
int n,m,x,y,c;
vector<pii> ans;
int main() {
	in>>n>>m;
	for(int i=1;i<=m;++i) {
		in>>x>>y>>c;
		vec[x].push_back(make_pair(y,c));
		vec[y].push_back(make_pair(x,c));
	}
	included[1] = true;
	dist[1] = 0;
	for(int i=2; i<=n; ++i) {
		dist[i] = inf;
	}
	for(auto [x, c]: vec[1]) {
		if(dist[x] != inf) {
			if(dist[x] > c and !included[x]) {
				s.erase(s.find(make_pair(dist[x], x)));
				s.insert(make_pair(c, x));
				unde[x] = 1;
				dist[x] = c;
			}
		} else {
			s.insert(make_pair(c, x));
			unde[x] = 1;
			dist[x] = c;
		}
	}
	int sum = 0;
	for(int iter=2; iter<=n; ++iter) {
		int nod = (*s.begin()).second;
		s.erase(s.begin());
		included[nod] = true;
		sum += dist[nod];
		ans.push_back(make_pair(unde[nod], nod));
		for(auto [x, c]: vec[nod]) {
			if(dist[x] != inf) {
				if(dist[x] > c and !included[x]) {
					s.erase(s.find(make_pair(dist[x], x)));
					s.insert(make_pair(c, x));
					unde[x] = nod;
					dist[x] = c;
				}
			} else {
				s.insert(make_pair(c, x));
				unde[x] = nod;
				dist[x] = c;
			}
		}
	}
	out<<sum<<'\n';
	out<<ans.size()<<'\n';
	for(auto [x, y]: ans) {
		out<<x<<' '<<y<<'\n';
	}
	return 0;
}