#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define NMaxVf 10000
#define Inf 600000
int n,m,VfMin,r,nrv;
double c[NMaxVf][NMaxVf],cmin[NMaxVf],CostMin;
int p[NMaxVf],z[NMaxVf];
void init(){
    int i,j,x,y;
    double q;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            c[i][j]=Inf;
    for(i=1;i<=n;i++){
        c[i][i]=0;
        for(j=1;j<=m;j++){
            f>>x>>y>>q;
            c[x][y]=c[y][x]=q;}
    }
    r=1;
    for(i=1;i<=n;i++){
        cmin[i]=c[r][i];
        p[i]=r;
        z[i]=1;}
    z[r]=0;p[r]=0;nrv=n-1;
}
void afis(){
    int i,k=0;
    double cost=0;
    for(i=1;i<=n;i++)
        if(i!=r){
            cost+=c[i][p[i]];
            k++;}
    g<<cost<<'\n'<<k<<'\n';
    for(i=1;i<=n;i++)
        if(i!=r)
            g<<p[i]<<' '<<i<<'\n';
}
int main()
{
    init();
    while(nrv){
        CostMin=Inf;
        for(int i=1;i<=n;i++)
            if(z[i] && CostMin>cmin[i]){
                CostMin=cmin[i];
                VfMin=i;}
            z[VfMin]=0;
            nrv--;
        for(int i=1;i<=n;i++)
            if(z[i] && c[i][VfMin]<cmin[i]){
                p[i]=VfMin;
                cmin[i]=c[i][VfMin];}
    }
    afis();
    return 0;
}