#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct muchie
{
	int inc, sf, cost;
	muchie(){}
	muchie(int a, int b, int c) { inc = a; sf = b; cost = c; }
};

bool compfunc(muchie a, muchie b) { return a.cost < b.cost; }

vector<muchie> muchii, apm;

int n, m, costapm;

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	int i, j, x, y, c;

	scanf("%d %d", &n, &m);

	int comp[n+1], //in care componenta se afla
        cate[n+1]; //cate noduri sunt in fiecare componenta

	for(i = 1;i <= m;i++)
	{
		scanf("%d %d %d", &x, &y, &c);
		muchii.push_back(muchie(x, y, c));
		comp[i] = i;
		cate[i] = 1;
	}

	sort(muchii.begin(), muchii.end(), compfunc);

	for(i = 0;i < m;i++)
	{
		if(comp[muchii[i].inc] != comp[muchii[i].sf])
		{
			apm.push_back(muchii[i]);
			costapm += muchii[i].cost;

			x = comp[muchii[i].inc];
			y = comp[muchii[i].sf];

			for(j = 0;j < m;j++)
			{
			    if(cate[x] == cate[y] || (comp[j] == x && cate[y] > cate[x]))
			    {
                    comp[j] = y;
                    cate[y]++;
			    }

                if(comp[j] == y && cate[x] > cate[y])
                {
                    comp[j] = x;
                    cate[x]++;
                }
			}
		}
	}

	printf("%d\n%d\n", costapm, n - 1);

	for(i = 0;i < (signed)apm.size();i++)
		printf("%d %d\n", apm[i].sf, apm[i].inc);
}