#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<fstream>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int mat[100][100],v[100],n,m,a[100],b[100];

void citire()
{
    int i,j,k,c;
     f>>n>>m;
     for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            mat[i][j]=mat[j][i]=0;

     for(int k=1;k<=m;k++)
        {
            f>>i>>j>>c;
          mat[i][j]=mat[j][i]=c;
        }
}

void prim()
{
	int x, y, i, j, k, minim,d=1;
	citire();
	int sum = 0,contor=0;
	v[1] = 1;
	for (k = 1; k < n; k++)
	{
		minim = 1000;
		for (i = 1; i < m; i++)
		for (j = 1; j < m; j++)
		if (v[i] && !v[j]  && mat[i][j]!=0)
            if(minim>mat[i][j])
		{
			minim = mat[i][j];
			x = i; y = j;
		}
		v[y] = 1;
		a[d]=x;b[d++]=y;
		sum += minim;
		contor++;
	}
 g<<sum<<"\n";
 g<<contor<<"\n";
 for(d=1;d<=contor;d++)
    g<<a[d]<<" "<<b[d]<<"\n";
}

int main()
{

prim();
f.close();
g.close();
return 0;
}