#include<fstream>

using namespace std;
#define INF 32000

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,costs[100],C[100],p[100];
int a[100][100];

void citire()
{
    fin>>n>>m;
    int x,y,c,i;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        a[x][y]=c;
        a[y][x]=c;
    }
    int r=1;
    for(i=1;i<=n;i++) {if(a[r][i]){costs[i]=a[r][i];}else costs[i]=INF; C[i]=1; p[i]=r;}
    C[r]=0;
    p[r]=0;
    fin.close();
}

void rezolva()
{
    int i;
    for(int j=1;j<n;j++)
    {
        int aux=INF,minv=-1;
        for(i=1;i<=n;i++)
            if(C[i] && aux>costs[i])
            { aux=costs[i]; minv=i;}
        C[minv]=0;
        for(i=1;i<=n;i++)
            if(C[i] && a[minv][i]<costs[i] && a[minv][i])
            {p[i]=minv; costs[i]=a[minv][i];}
    }
}

void afisare(int r)
{
    int i,cost=0,nrm=0;
    for(i=1;i<=n;i++) if(i!=r && a[p[i]][i]) cost+=costs[i],nrm++;
    fout<<cost<<'\n'<<nrm<<'\n';
    for(i=1;i<=n;i++) if(i!=r && a[p[i]][i]) fout<<p[i]<<" "<<i<<"\n";
    fout.close();
}

int main()
{
    citire();
    rezolva();
    afisare(1);

    fin.close();
    fout.close();
    return 0;
}