#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],total;
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;

    for(i=1; i<=n; i++)
        if(i!=r && a[p[i]][i]) total+=costs[i];
    fout<<total<<"\n"<<n-1<<"\n";
    for(i=1; i<=n; i++)
        if(i!=r && a[p[i]][i]) fout<<i<<" "<<p[i]<<"\n";
    fout.close();
}

int main()
{
    citire();
    rezolva();
    afisare(1);
    return 0;
}