#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<map>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<vector>
#include<stack>
#include<queue>
#include<limits>
#define all(v) v.begin(),v.end()
#define sorti(v) sort(all(v))
#define desc(x) greater<x>()
#define lsb(x) ((x)&(-x))
#define sortd(v) sort(all(v),desc(decltype(v[0])))
#define hmap unordered_map 
#define var auto&
#define hset unordered_set
#define pq priority_queue
#define inf 0x3f3f3f3f
#define exists(x,v) (v.find(x)!=v.end())
#define inrange(x,a,b) (x>=a && x<=b)
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
template<typename T> T gcd(T a, T b) { T c; while (b) { c = a % b; a = b; b = c; }return a; }
template<typename T> T exp(T a, T n, T m) { T p = 1; while (n) { if (n & 1)p = (p % m * a % m) % m; a = (a % m * a % m) % m; n >>= 1; }return p; }
template<typename T> T exp(T a, T n){T p = 1; while (n) { if (n & 1)p *= a; a *= a;  n >>= 1; }return p;}
template<typename T> T invm(T a, T m) {return exp(a, m - 2, m);}
const int lim = 2e5;
int rang[lim];
int T[lim];
int n, m;
struct muchie
{
	int src, dest, c;
	muchie(int src, int dest, int  c) :src(src), dest(dest), c(c) {};
};
vector<muchie> muchii;
vector<int> sol;
int ans;
int best[lim];

int find(int x)
{
	if (!T[x])
		return x;
	return x = find(T[x]);
}
void unite(int x, int y)
{
	int tx = find(x), ty = find(y);
	if (tx != ty)
	{
		if (rang[tx] > rang[ty])
			T[ty] = tx;
		else
		{
			T[tx] = ty;
			if (rang[tx] == rang[ty])
				rang[ty]++;
		}
	}
}
void apm()
{
	for (int i = 1; i <= n; i++)
		best[i] = -1;
	int nrComp = n;
	while (nrComp > 1)
	{
		for (int i = 1; i <= n; i++)
			best[i] = -1;
		for (int i = 0; i < m; i++)
		{
			int tsrc = find(muchii[i].src);
			int tdest = find(muchii[i].dest);
			if (tsrc == tdest)
				continue;
			else
			{
				if (best[tsrc] == -1 || (muchii[best[tsrc]].c > muchii[i].c))
					best[tsrc] = i;

				if (best[tdest] == -1 || (muchii[best[tdest]].c > muchii[i].c))
					best[tdest] = i;
			}

		}
		for(int i=1;i<=n;i++)
			if (best[i] != -1)
			{
				int tsrc = find(muchii[best[i]].src);
				int tdest = find(muchii[best[i]].dest);
				if (tdest == tsrc)
					continue;
				ans += muchii[best[i]].c;
				unite(tsrc, tdest);
				sol.push_back(best[i]);
				nrComp--;
			}
			
	}
}


int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y,c;
		cin >> x >> y >> c;
		muchii.push_back(muchie(x, y, c));
	}
	apm();
	cout << ans << '\n' << sol.size() << '\n';
	for (auto it : sol)
		cout << muchii[it].src << " " << muchii[it].dest << '\n';
}