#include <fstream>
#include <stdint.h>
#define nmax 200001
#define mmax 400001
using namespace std;
fstream f1("apm.in", ios::in);
fstream f2("apm.out", ios::out);
int32_t n, m, t[nmax], nr, cost, siz[nmax];
int32_t aux[nmax], nrc;
struct muchii
{
    int32_t x, y, c;
} muc[mmax];
int32_t sol, nrm;
struct solutie
{
    int32_t x, y;
}a[mmax];
void quicksort(int32_t st, int32_t dr)
{
    int32_t i=st, j=dr, pivot=muc[(st+dr)/2].c;
    while(i<=j)
    {
        while((muc[i].c<pivot)&&(i<dr)) i++;
        while((muc[j].c>pivot )&&(j>st)) j--;
        if(i<=j)
        {
            swap(muc[i], muc[j]);
            i++;
            j--;

        }
    }
    if(st<j) quicksort(st, j);
    if(i<dr) quicksort(i, dr);

}
void citire()
{
    int32_t i, x, y, c;
    f1>>n>>m;

    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        muc[i].x=x;
        muc[i].y=y;
        muc[i].c=c;
    }
}
int32_t Find(int32_t x)
{
    int32_t i;
    nrc=0;
    while(t[x]!=0)
    {
        nrc++;
        aux[nrc]=x;
        x=t[x];
    }
    for(i=1; i<=nrc; i++)
        t[aux[i]]=x;
    return x;
}
void Union(int32_t rx, int32_t ry)
{
    if(siz[rx]> siz[ry]) {t[ry]=rx; siz[rx]+=siz[ry];}
    else {t[rx]=ry; siz[ry]+=siz[rx];}
}
void kruskal_optimizat()
{
    int32_t i, x, y, rx, ry;
    for(i=1; i<=m; i++)
    {
        x=muc[i].x;
        y=muc[i].y;
        rx=Find(x);
        ry=Find(y);
        if(rx!=ry)///daca unesti noduri din subarbori disjuncti
        {
            Union(rx, ry);
            nrm++;
            sol+=muc[i].c;
            a[nrm].x=x;
            a[nrm].y=y;
        }
    }
}
void init()
{
    int32_t i;
    for(i=1;i<=n; i++)
        siz[i]=1;
}
void afisare()
{
    int32_t i;
    f2<<sol<<"\n"<<nrm<<"\n";
    for(i=1; i<=nrm; i++)
        f2<<a[i].y<<" "<<a[i].x<<"\n";
}
int main()
{
    citire();
    ///sortezi de la 1 la m muchiile in fct de cost
    quicksort(1, m);
    init();
    kruskal_optimizat();
    afisare();
    return 0;
}