#include <bits/stdc++.h>

using namespace std;

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

int parinte[200001], n, m, q;

struct muchie
{
	int x, y, cost;
};
vector<muchie> sol;
vector<muchie> v;

int cost_cmp(muchie a, muchie b){
	return a.cost < b.cost;
}

int Find(int x)
{
    if (parinte[x] == x)
        return x;
    parinte[x] = Find(parinte[x]);
    return parinte[x];

}

void Union(int x, int y)
{
	parinte[Find(x)] = Find(y);
}

int main()
{
	fin >> n >> m;

	for (int i = 1; i <= m; ++i){
        muchie mch;
		fin >> mch.x >> mch.y >> mch.cost;
        v.push_back(mch);
	}
    //sortam muchiile dupa cost
	sort(v.begin(), v.end(), cost_cmp);


    //configuram pt kruskal
	for (int i = 0; i < n; ++i)
		parinte[i] = i;


    int cost_min=0;
	//kruskal propriu zis
	for (int i = 0; i < m; ++i)
	{

		if (Find(v[i].x) != Find(v[i].y)){
			Union(Find(v[i].x), Find(v[i].y));
            cost_min += v[i].cost;
            sol.push_back(v[i]);
        }
    }

    fout<<cost_min<<endl<<(int)sol.size()<<endl;
    for(int i=0; i<(int)sol.size(); i++)
        fout<<sol[i].x<<' '<<sol[i].y<<endl;

}