#include <fstream>
#include <algorithm>
#define NMAX 2001
#define MMAX 400001
using namespace std;

ofstream fout("apm.out");

struct vecin
{
    int vf;
    int cost;
};
vecin L[NMAX][NMAX];
int n, m, start;
int z[NMAX], cmin[NMAX], pre[NMAX];
int total;

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

int main()
{
    citire();
    start=1;
    prim(start);
    afisare();
    return 0;
}

void citire()
{
    ifstream fin ("apm.in");
    int i, x, y, z;
    fin>>n>>m;
    for(i=1; i<=m; ++i)
    {
        fin>>x>>y>>z;
        L[x][++L[x][0].vf].vf=y;
        L[x][L[x][0].vf].cost=z;
        L[y][++L[y][0].vf].vf=x;
        L[y][L[y][0].vf].cost=z;
    }

}

void prim (int start)
{
    initializare(start);
    int i, j, pmin;
    for(i=1; i<n; ++i)
    {
        pmin=n+1;
        for(j=1; j<=n; ++j)
            if(cmin[j]<cmin[pmin] && !z[j])
            pmin=j;
        z[pmin]=1;
        total+=cmin[pmin];
        for(j=1; j<=L[pmin][0].vf; ++j)
            if(cmin[L[pmin][j].vf]>L[pmin][j].cost)
            {
                cmin[L[pmin][j].vf]=L[pmin][j].cost;
                pre[L[pmin][j].vf]=pmin;
            }

    }
}

void initializare(int start)
{
    int i, j, infinit=1000;
    cmin[n+1]=infinit;
    for(i=1; i<=n; ++i)
        if(i!=start)
        {
            pre[i]=start;
            for(j=1; j<=L[start][0].vf; ++j)
                if(L[start][j].vf==i)
                cmin[i]=L[start][j].cost;
            if(!cmin[i]) cmin[i]=infinit;
        }
    z[start]=1;
}

void afisare()
{
    int i;
    fout<<total<<'\n'<<n-1<<'\n';
    for(i=1; i<=n; ++i)
        if(i!=start)
        fout<<i<<' '<<pre[i]<<'\n';
    fout.close();
}