#include <fstream>
#define INF 10000001

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

int n, m, start, cmin[1000];
int M[1000], tata[1000], v[1000];
int cost, muchii;
struct lista
{
    int x,co;
}g[1000][1000];

void citire();
void initializare();
void prim();
void afisare();

int main()
{
    citire();
    initializare();
    prim();
    afisare();

    fout.close();
    return 0;
}

void citire()
{
    int i, lin, col, c;
    fin>>n>>m;
    start=1;
    for(i=1; i<=n; i++)
    {
        fin>>lin>>col>>c;
        g[lin][++v[lin]].x=col;
        g[col][++v[col]].x=lin;
        g[lin][v[lin]].co=c;
        g[col][v[col]].co=c;
    }
    for(i=1; i<=v[start]; i++)
        cmin[g[start][i].x]=g[start][i].co;
}

void initializare()
{
    int i;
    M[0]=start;
    //for(i=1; i<=v[start]; i++)
        //cmin[g[start][i].x]=g[start][i].co;
    for(i=1; i<=n; i++)
    {
        if(g[start][i].co!=0)
            cmin[g[start][i].x]=g[start][i].co;
        else
            cmin[i]=INF;
        if(i!=start)
            tata[i]=start;
    }
    cmin[start]=0;
    tata[start]=0;
}

void prim()
{
    int i, j, neviz=n-1, nrmin, vf;
    for(i=1; i<=n-1; i++)
    {
        nrmin=INF+1;
        for(j=1; j<=n; j++)
            if(!M[i]&&nrmin>cmin[i]) //fgf
            {
                nrmin=cmin[i];
                vf=i;//fgf
                //g[vf][tata[vf]]=cmin[i];
            }
        M[vf]=1;
        //fout<<vf<<' '<<tata[vf]<<'\n';
        //g[vf][tata[vf]]=cmin[i];
        for(i=1; i<=cmin[vf]; i++)
            if(!M[g[vf][i].x] && cmin[g[vf][i].x]>g[vf][i].co)
            {
                tata[g[vf][i].x]=vf;
                cmin[g[vf][i].co]=g[vf][i].co;
            }
    }
}

void afisare()
{
    int i, j;
    /*for(i=1; i<=n; i++)
        cost+=cmin[i];
    fout<<cost<<'\n'<<n-1<<'\n';
    for(i=2; i<=n; i++)
        fout<<i<<' '<<tata[i]<<'\n';*/
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(g[i][j].co!=0)
            {
                cost=cost+g[i][j].co;
                muchii++;
            }
    fout<<cost<<'\n';
    fout<<muchii/2<<'\n';
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(g[i][j].co!=0 && g[j][i].co==0)
            {
                fout<<i<<' '<<j<<'\n';
                g[i][j].co=0;
            }
}