#include <fstream>
#define inf 1000000000
#define Dmax 12500
using namespace std;
ifstream intrare("apm.in");
ofstream iesire("apm.out");
int n,m,start=1;
int cmin[Dmax],uz[Dmax],tata[Dmax],v[Dmax],A[Dmax][Dmax],cm;
struct lista{int x,co;}G[Dmax][Dmax];
void citire();
void prim();
int main()
{
	int i,j;
    citire();
    prim();
	for(i=1;i<=n;i++)
		cm+=cmin[i];
	iesire<<cm<<'\n';
	iesire<<n-1<<'\n';
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(A[i][j]==1)
				iesire<<i<<' '<<j<<'\n';
}
void citire()
{
    int i,l,c,cost;
    intrare>>n>>m;
    //intrare>>start;
    for(i=1;i<=m;i++) 
    {
        intrare>>l>>c>>cost;
        G[l][++v[l]].x=c;
        G[c][++v[c]].x=l;
        G[l][v[l]].co=cost;
        G[c][v[c]].co=cost; 
    }
    uz[0]=1;
    uz[start]=1;
    for(i=1;i<=v[start];i++)
        cmin[G[start][i].x]=G[start][i].co;
    for(i=1;i<=n;i++)
    {
        if(cmin[i]==0)
            cmin[i]=inf;
        tata[i]=start;
    }
    tata[start]=0;
    cmin[start]=0;
}
void prim()
{
    int i,costmin,j,k,minimvf,tatavf;
    for(i=1;i<=n-1;i++)
    {
        while(uz[0]<n)
        {
            costmin=inf; 
            for(j=1;j<=n;j++)
                if(uz[j])
                {
                    for(k=1;k<=v[j];k++)
                        if(G[j][k].co<costmin && uz[G[j][k].x]==0)
                        {
                            costmin=G[j][k].co;
                            minimvf=G[j][k].x;
                            tatavf=j;
                        }
                }
            tata[minimvf]=tatavf;
            cmin[minimvf]=costmin;
            uz[minimvf]=1;
            A[minimvf][tata[minimvf]]=1;
            uz[0]++;
        }
    }
}