#include <fstream>
#include <vector>
#define NMAX 200001
#define MMAX 400001
using namespace std;

ofstream fout("apm.out");

struct vecin
{
    int vf;
    int cost;
};
vector <vecin> L[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;
    vecin aux;
    fin>>n>>m;
    for(i=1; i<=m; ++i)
    {
        fin>>x>>y>>aux.cost;
        aux.vf=y;
        L[x].push_back(aux);
        aux.vf=x;
        L[y].push_back(aux);

    }

}

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=0; j<L[pmin].size(); ++j)
            if(cmin[L[pmin][j].vf]>L[pmin][j].cost && !z[L[pmin][j].vf])
            {
                cmin[L[pmin][j].vf]=L[pmin][j].cost;
                pre[L[pmin][j].vf]=pmin;
            }

    }
}

void initializare(int start)
{
    int i, j, infinit=1009;
    cmin[n+1]=infinit;
    for(i=1; i<=n; ++i)
        if(i!=start)
        {
            pre[i]=start;
            for(j=0; j<L[start].size(); ++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();
}