#include <cstdio>
#include <set>
#include <vector>
#include <string>
#include <cstring>

#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f
#define vii vector <pair <int, int > > :: iterator
#define sii set <pair <int, int> > :: iterator

const int maxn = 200005;

using namespace std;

int d[maxn], X[maxn], Y[maxn], t[maxn];
char viz[maxn];
int cost;
vector <pair <int, int> > g[maxn];
set <pair <int, int> > myset;
int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	
	int n, m, x, y, c;

	for( scanf("%d %d\n", &n, &m); m--; ) {
		scanf("%d %d %d", &x, &y, &c);
		g[x].pb(mp(y, c));
		g[y].pb(mp(x, c));
	}
	
	memset(d, inf, sizeof(d));
	d[1] = 0;
	for(vii it = g[1].begin(); it != g[1].end(); ++it) {
		myset.insert(mp( it -> second, it -> first) );
		d[it -> first] = it -> second;
		t[it -> first] = 1;
	}
	viz[1] = 1;

	for(int i = 1; i < n; ++i) {
		int curr_node;
		
		sii it1 = myset.begin(); myset.erase(it1);
		curr_node = it1 -> second;
		cost += it1 -> first;
		viz[curr_node] = 1;
		
		X[++X[0]] = t[curr_node]; 
		Y[++Y[0]] = curr_node;
		
		for(vii it = g[curr_node].begin() ; it != g[curr_node].end(); ++it) {
			int tmp_node = it -> first;
			int tmp_cost = it -> second;
			if(viz[tmp_node]) continue;
			
			if(d[tmp_node] > tmp_cost) {
				sii it2;
				it2 = myset.find( mp( d[tmp_node] , tmp_node) );
				if(it2 != myset.end()) 
					myset.erase(it2);
				d[tmp_node] = tmp_cost;
				t[tmp_node] = curr_node;
				myset.insert( mp( d[tmp_node], tmp_node) );
			}
		}
	}
	
	printf("%d\n%d\n", cost, X[0]);
	for(int i = 1; i <= X[0]; ++i)
		printf("%d %d\n", X[i], Y[i]);
	return 0;
}