#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;

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

const int NMAX = 4e5 + 5;
int t[NMAX], r[NMAX], total;
vector<pair<int, int>> er;

struct edge{
	int x, y, p;
}v[NMAX];

bool srt(edge a, edge b){return a.p < b.p;}

int FindT(int nod)
{
	while(t[nod] != nod)
		nod = t[nod];
	return nod;
}

void UN(int nx, int ny)
{
	if(r[nx] < r[ny]) t[nx] = ny;
	else if(r[nx] > r[ny]) t[ny] = nx;
	else t[nx] = ny, ++r[ny];
}

int main() 
{
	ios::sync_with_stdio(false);
	fin.tie();

	int n, m;

	fin >> n >> m;

	for(int i = 1; i <= m; ++i)
		fin >> v[i].x >> v[i].y >> v[i].p;
	for (int i = 1; i <= m; ++i)
		t[i] = i, r[i] = 1;

	sort(v + 1, v + m + 1, srt);

	for(int i = 1; i <= m; ++i)
	{
		int auxf1 = FindT(v[i].x), auxf2 = FindT(v[i].y);
		if(auxf1 != auxf2)
		{
			UN(auxf1, auxf2);
			er.push_back({v[i].x, v[i].y});
			total += v[i].p;
		}
	}

	fout << total << "\n" << er.size() << "\n";
	
	for (auto i : er)
		fout << i.second << " " << i.first << "\n";
	
	return 0; 
}