#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("apm.in", ios::in);
fstream f2("apm.out", ios::out);
///kruskal:
int32_t n, m, v[200001], nr, cost;
struct muchii
{
    int32_t x, y, c;
}a[200000], muc[400001];

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);
}

int main()
{
    int32_t i, j, x, y, c, schimb,mini;
    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;
    }

    ///sortezi de la 1 la m muchiile in fct de cost
    quicksort(1, m);
    //for(i=1; i<=m; i++)
    //   f2<<muc[i].x<<" "<<muc[i].y<<" "<<muc[i].c<<"\n";
    //f2<<"..................................."<<"\n";

    ///init v
    for(i=1; i<=n; i++) v[i]=i;
    ///cauti muchiile in fct de cost in ordina sortata
    for(i=1; (nr<(n-1)) && (i<=m); i++)
        if(v[muc[i].x]!=v[muc[i].y])
        {
            ///selectezi muchia
            nr++;
            a[nr].x=muc[i].x;
            a[nr].y=muc[i].y;
            a[nr].c=muc[i].c;

            ///unifici cei doi arbori pastrand in minimul dintre v[i] si v[x]
            if(v[muc[i].x]>v[muc[i].y])
              {schimb=v[muc[i].x];mini=v[muc[i].y];}///x este mai mare
            else
              {schimb=v[muc[i].y];mini=v[muc[i].x];}
            for(j=1; j<=n; j++)
                if(v[j]==schimb) v[j]=mini;

            ///reactualizezi costul
            cost+=muc[i].c;
        }

    ///afisarea
    f2<<cost<<"\n"<<nr<<"\n";
    for(i=1; i<n; i++)
       f2<<a[i].x<<" "<<a[i].y<<"\n";

    return 0;
}