#include <bits/stdc++.h>

using namespace std;

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

const int MMAX = 4e5 + 100;
const int NMAX = 2e5 + 100;

struct Muchie{int st, dr, d;}MC[MMAX];

int N, M, T[NMAX], H[NMAX], sol;
vector <int> ARB;

bool cmp(const Muchie &A, const Muchie &B)
{
	return A.d < B.d;
}

int Find(int x)
{
    int tat, r = x, y = x;
    while(T[r])r = T[r];
    while(y != r)
    {
        tat = T[y];
        T[y] = r;
        y = tat;
    }
    return r;
}

void Unite(int x, int y)
{
    if(H[x] > H[y])T[y] = x;
    else
    {
        T[x] = y;
        if(H[x] == H[y])H[y]++;
    }
}

int main()
{
	fin >> N >> M;
	fill(H + 1, H + N + 1, 1);
	for(int i = 1; i <= M; ++i)
	{
		fin >> MC[i].st >> MC[i].dr >> MC[i].d;
	}
	sort(MC + 1, MC + M + 1, cmp);
	for(int i = 1; i <= M and ARB.size() < N; ++i)
    {
        int st = MC[i].st, dr = MC[i].dr;
        st = Find(st), dr = Find(dr);
        if(st != dr)
        {
            Unite(st, dr);
            ARB.push_back(i);
            sol += MC[i].d;
        }
    }
    fout << sol << '\n' << ARB.size() << '\n';
    for(int i = 0; i < ARB.size(); i++)
    {
    	fout << MC[ARB[i]].st << ' ' << MC[ARB[i]].dr << '\n';
    }
	return 0;
}