#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 200005
#define INF 1<<30
#define pii pair<int, int>
#define mk make_pair
#define min(a, b) (((a) < (b)) ? (a) : (b))
using namespace std;

struct compar{
	bool operator() (pii a, pii b) {return a.second > b.second;}
};

int n, m, x, y, z, p[MAX], d[MAX], cost;
bool incl[MAX];
vector<pii> l[MAX], arb;
priority_queue<pii, vector<pii>, compar> pq;

void prim(){
	for(int i = 1; i <= n; i++){
		d[i] = INF;
		p[i] = 0;
	}
	d[1] = 0;

	pq.push(pii(1, d[1]));
	while(!pq.empty()){
		pii aux = pq.top();
		int node = aux.first;
		pq.pop();
		
		if(incl[node])
			continue;
		if(p[node])
			arb.push_back(mk(node, p[node]));
		incl[node] = 1;
		cost += aux.second;

		for(int i = 0; i < l[node].size(); i++)
			if(d[l[node][i].first] > l[node][i].second){
				d[l[node][i].first] = l[node][i].second;
				p[l[node][i].first] = node;
				pq.push(mk(l[node][i].first, d[l[node][i].first]));
			}
	}
}

int main(){
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++){
		scanf("%d%d%d", &x, &y, &z);
		l[x].push_back(mk(y, z));
		l[y].push_back(mk(x, z));
	}
	prim();
	printf("%d\n", cost);
	printf("%d\n", arb.size());
	for(int i = 0; i < arb.size(); i++)
		printf("%d %d\n", arb[i].first, arb[i].second);
	return 0;
}