#include <fstream>
#define NMAX 1000
#define INF 10000001

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

int n, m, start, g[NMAX][NMAX], cmin[NMAX];
int M[NMAX], tata[NMAX];
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+1;
        for(j=1; j<=n; j++)
            if(M[j]==0&&nrmin>cmin[i])
            {
                nrmin=cmin[i];
                vf=j;
            }
        g[vf][tata[vf]]=cmin[i];
        M[vf]=1; cost+=nrmin;
            for(x=1; x<=n; x++)
                if(!M[g[vf][j]] && cmin[x]>cmin[vf]+g[vf][x])
                {
                    cmin[x]=cmin[vf]+g[vf][x];
                    tata[x]=vf; M[x]=1;
                }
    }
}

void afisare()
{
    int i, j;
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(i=1; i<=n; i++)
        fout<<i<<' '<<tata[i]<<'\n';
}