#include <fstream>
#define NMAX 200002
#define MMAX 400002

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

struct Muchie
{
    int x, y, cost;
    friend bool operator < (Muchie a, Muchie b);
    friend bool operator > (Muchie a, Muchie b);
    friend bool operator <= (Muchie a, Muchie b);
    friend bool operator >= (Muchie a, Muchie b);
};
bool operator < (Muchie a, Muchie b)
{
    return a.cost<b.cost;
}
bool operator > (Muchie a, Muchie b)
{
    return a.cost>b.cost;
}
bool operator <= (Muchie a, Muchie b)
{
    return a.cost<=b.cost;
}
bool operator >= (Muchie a, Muchie b)
{
    return a.cost>=b.cost;
}
int n, m, tata[NMAX], h[NMAX], nrsel, costtotal, cx, cy, aux;
Muchie H[MMAX], A[NMAX];

void creare();
void combinare(int n, Muchie H[], int poz);
Muchie extrageMin(int &n, Muchie H[]);
void Union(int x, int y);
int Find(int x);

int main()
{
    Muchie mmin;
    creare();
    while(nrsel<n-1)
    {
        mmin=extrageMin(m, H);
        cx=Find(mmin.x);
        cy=Find(mmin.y);
        if(cx!=cy)
        {
            nrsel++;
            A[nrsel]=mmin;
            costtotal+=mmin.cost;
            Union(cx,cy);
        }
    }
    fout<<costtotal<<'\n';
    fout<<n-1<<'\n';
    for(int i=1;i<n;++i)
        fout<<A[i].x<<' '<<A[i].y<<'\n';
    fout.close();
    return 0;
}

void combinare(int n, Muchie H[], int poz)
{
    Muchie x=H[poz];
    int fiu, tata;
    tata=poz;
    fiu=2*tata;
    while (fiu<=n)
    {
        if (fiu+1<=n && H[fiu+1]<H[fiu]) fiu++;
        if (x <= H[fiu]) break;
        H[tata]=H[fiu];
        tata=fiu;
        fiu=2*tata;
    }
    H[tata]=x;
}

void creare()
{
    int i;
    fin>>n>>m;
    for (i=1; i<=m; i++) fin>>H[i].x>>H[i].y>>H[i].cost;
    for (i=m/2; i>0; i--)
        combinare(m, H, i);
}

Muchie extrageMin(int &n, Muchie H[])
{
    Muchie minim=H[1];
    H[1]=H[n--];
    combinare(n,H,1);
    return minim;
}

int Find(int x)
{
    int rad=x, aux;
    while(tata[rad])
        rad=tata[rad];
    ///compresia drumului
    while(tata[x])
    {
        aux=tata[x];
        tata[x]=rad;
        x=aux;
    }
    return rad;
}
void Union(int x, int y)
{
    if(h[x]<h[y]) tata[x]=y;
    else
    {
        tata[y]=x;
        if(h[x]==h[y]) h[x]++;
    }
    tata[y]=x;
    ///O(1)
}