// Prim's Algorithm


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

#define vit vector <pair <int, int> > :: iterator
#define sit set <pair <int, int> > :: iterator
#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 200005;

set <pair <int, int> > myset;
vector <pair <int, int> > g[maxn];
bitset <maxn> vis;
int cost, n, m;
int x[maxn], y[maxn], tt[maxn], d[maxn]; 
int main() {

	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);


	for( scanf("%d%d\n", &n, &m); m--; ) {
		int a, b, c;
		scanf("%d %d %d\n", &a, &b, &c);
		g[a].pb(mp(b, c)); g[b].pb(mp(a, c));
	}
	
	for(int i = 1; i <= n; i++) d[i] = inf;
	
	for(vit it = g[1].begin(); it != g[1].end(); it++) {
		d[it -> f] = it -> s;
		myset.insert(mp(it -> s, it -> f)); tt[it -> f] = 1;
	}
	vis[1] = true;

	for(int i = 1; i < n; i++) {
		sit it2 = myset.begin(); myset.erase(it2);
		int node = it2 -> second; 
		cost += it2 -> first;
		vis[node] = 1;
		
		x[++x[0]] = tt[node]; y[++y[0]] = node;

		for(vit it = g[node].begin(); it != g[node].end(); it++)
			if(!vis[it -> f] && d[it -> f] > it -> s) {
				it2 = myset.find(mp(d[it -> f], it -> f));
				tt[it -> f] = node;	
				if(it2 != myset.end())
					myset.erase(it2);

				d[it -> f] = it -> s;
				myset.insert(mp(it -> s, it -> f));
			}
	}
	
	printf("%d\n%d\n", cost, n - 1);
	for(int i = 1; i < n; i++)
		printf("%d %d\n", x[i], y[i]);

	return 0;
}