#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct lol{
	int x, y, c;
};

int n, m, p[400100], rs; lol a[400100]; 
vector <int> v;

bool cmp(lol a, lol b){
	return (a.c < b.c);
}

int find(int a){
	return (p[a] == a ? a : p[a] = find(p[a]));
}

void unite(int a, int b){
	p[find(a)] = b;
}

int main(){
	in >> n >> m;
	for(int i = 1; i <= m; i++)
		in >> a[i].x >> a[i].y >> a[i].c;
	sort(a+1, a+m+1, cmp);
	for(int i = 1; i <= n; i++) p[i] = i;
	for(int i = 1; i <= m; i++)  
		if(find(a[i].x) != find(a[i].y)){
			rs += a[i].c;
			v.push_back(i);
			unite(a[i].x, a[i].y);
		}
	out << rs << '\n' << v.size() << '\n';
	for(auto i : v) out << a[i].x << ' ' << a[i].y << '\n';
	return 0;
}