#include <fstream>
using namespace std;


int n, m;
struct muchie{
    int v1, v2;
    int val;
};

muchie a[100];
muchie arb[100];
int p[100];
int h[100];
int cost;


ifstream fin("apm.in");
ofstream fout("apm.out");
void Read();
void Sort();
void Init();
int Cauta(int);
void Unire(int, int);
void Afis();
void Kruskal();





int main()
{
    Read();
    Kruskal();
    Afis();
    
    
    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> n;
    fin >> m;
    for (int i = 1; i<=m; i++)
    {
        fin >> a[i].v1;
        fin >> a[i].v2;
        fin >> a[i].val;
    }
}

void Sort()
{
	for ( int i = 1; i < m; i++ )
		for ( int j = i + 1; j <= m; j++ )
			if ( a[j].val < a[i].val )
			{
				muchie aux = a[i];
				a[i] = a[j];
				a[j] = aux;
			}
	/*		
	for ( int i = 1; i <= m; i++ )
	{
	    fout << a[i].val << " ";
	}
  	fout << "\n";
  	*/
}

void Init()
{
    for (int i = 1; i<=n; i++)
    {
        p[i] = i;
        h[i] = 0;
    }
}

void Unire(int x, int y)
{
    if (h[x] > h[y])
    {
        p[y] = x;
    }
    else
    {
        p[x] = y;
        if (h[x] == h[y]) ++h[y];
    }
}

int Cauta(int x)
{
    if (x != p[x]) p[x] = Cauta(p[x]);
    return p[x];
}

void Kruskal()
{
    Sort();
    int k = 0;
    Init();
    
    for (int i = 1; i <= m; i++)
    {
        int r1 = Cauta(a[i].v1);
        int r2 = Cauta(a[i].v2);
        //fout << a[i].v1 << " " << a[i].v2 << "\n";
        if (r1 != r2)
        {
            cost += a[i].val;
            arb[++k] = a[i];
            Unire(r1, r2);
            if (k == n-1) break;
        }
    }
}

void Afis()
{
    fout << cost << "\n";
    fout << n-1 << "\n";
    for (int i = 1; i < n-1; i++)
    {
        fout << arb[i].v1 << " " << arb[i].v2 << "\n";
    }
}