#include<iostream>
#include<fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int inf=1500;
const int dim=23100;
int i,n,m,j,s[dim],k,x,y,t[dim],q[3][dim];
float cost,minn,a[dim][dim],c;

void citire(){
in>>n>>m;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)if(i==j)a[i][j]=0;
    else a[i][j]=inf;
for(i=1;i<=m;i++)
{in>>x>>y>>c;a[x][y]=a[y][x]=c;}
in.close();
}

void rez(){
for(i=2;i<=n;i++)
    s[i]=1;
for(i=1;i<n;i++)
{minn=inf;
for(j=1;j<=n;j++)
    if(s[j])if(a[s[j]][j]<minn)
{minn=a[s[j]][j];k=j;}
t[k]=s[k];
q[1][i]=s[k];
q[2][i]=k;
cost+=a[s[k]][k];s[k]=0;
for(j=1;j<=n;j++)
    if(s[j]&&a[j][s[j]]>a[j][k])s[j]=k;}
}

void afisare(){
out<<cost<<"\n";
out<<n-1<<"\n";
for(i=1;i<n;i++)
    out<<q[1][i]<<" "<<q[2][i]<<"\n";
}


int main(){citire();
rez();
afisare();
return 0;}