#include <fstream>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,mat[100][100],s[100],t[100],vazut[100],cost[100],r;
void afisare()
{   int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            out<<mat[i][j]<<" ";
            out<<endl;
    }

}
void cautare(int nod)
{   int i,j;
    for(i=1;i<=n;i++)
    {
    if(t[nod]!=i) if(mat[nod][i]<cost[i]&&mat[nod][i]!=0)
    {   cost[i]=mat[nod][i];
        t[i]=nod;

    }

    }
    vazut[nod]=1;
    r=nod+1;
    if(r<=n)
    cautare(r);

}

int main()
{   int x,y,c,i,j,mini=99999,costt=0;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {   in>>x>>y>>c;
        mat[x][y]=c;
        mat[y][x]=c;

    }
    for(i=1;i<=n;i++)
    {   cost[i]=99999;

    }
    cautare(1);
   // afisare();
    s[1]=1;
    t[1]=0;
    cost[1]=0;
    for(i=1;i<=n;i++)
    {costt=costt+cost[i];

    }out<<costt;
    out<<endl;
    out<<n-1;out<<endl;
    for(i=2;i<=n;i++)
    {   out<<t[i]<<" "<<i;
    out<<endl;

    }

    return 0;
}