#include <fstream>

using namespace std;

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

int n,t[500],d[500], m,cost[30][30],c,sum=0,nod,minim;
bool sel[500];

void apm(int x)
{
    int i,j;
    int nr=0;
    for(i=1;i<=n;i++)  d[i]=10000;
    d[x]=0; t[x]=0;
     for(i=1;i<=n;i++)
    {
        minim=10000;
        for(j=1;j<=n;j++)
            if(d[j]<minim && !sel[j])
            {
                minim=d[j];
                nod=j;
            }
        sel[nod]=true;
        sum+=d[nod];
        if (minim!=10000)nr++;
        for(j=1; j<=n; j++)
           if(cost[nod][j]< d[j] && !sel[j])
           {
               d[j] = cost[nod][j];
               t[j] = nod;
           }
    }
g<<sum<<"\n"<<n-1<<"\n";
    for (i=1; i<=n; i++)
      if (t[i]) g<<i<<" "<<t[i]<<'\n';
}
int main()
{
    int x,y,i,j;
    f>>n>>m;
    for(i=1;i<=n;i++)
        sel[i]=false;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cost[i][j]=10000;
    for(i=1;i<=n;i++)
        cost[i][i]=0;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        cost[x][y]=cost[y][x]=c;
    }

    apm(1);


    return 0;
}