#include <fstream>
#define INF 10000001

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

int n, m, start, g[1000][1000], cmin[1000];
int M[1000], tata[1000];
int cost, muchii;

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

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

    fout.close();
    return 0;
}

void citire()
{
    int i, x, y, c;
    fin>>n>>m;
    start=1;
    for(i=1; i<=n; i++)
    {
        fin>>x>>y>>c;
        g[x][y]=c;
    }
}

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

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

    /*int vfmin, i, x, nrmin, neviz=n-1;
    while(1)
    {
        nrmin=INF;
        for(i=1;i<=n;i++)
            if(!viz[i]&&nrmin>cmin[i])
            {
                nrmin=cmin[i]; vfmin=i;
            }
        if(neviz)
        {
            viz[vfmin]=1; neviz--;
            for(x=1;x<=n;x++)
                if(!viz[x]&&cmin[x]>cmin[vfmin]+c[vfmin][x])
                {
                    cmin[x]=cmin[vfmin]+c[vfmin][x];
                    tata[x]=vfmin;
                }
        }
        else break;
    }*/
}

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