#include <bits/stdc++.h>

using namespace std;

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

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

struct muchie
{
	int x, y, cost;
}v[100001], a[100001];
vector<muchie> sol;


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)
		fin >> v[i].x >> v[i].y >> v[i].cost;

    //sortam muchiile dupa cost
	sort(v + 1, v + m + 1, cost_cmp);


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


    int cost_min=0;
	//kruskal propriu zis
	for (int i = 1; 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;

}