#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int i,j,cost;
    bool ok;
}x[200000],v[200000];

int t[200000],rang[200000],n,m;

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>x[i].i>>x[i].j>>x[i].cost;
}

int radacina(int k)
{
    if(k!=t[k])
        k=radacina(t[k]);
    return k;
}

void ranguri(int k,int p)
{
    if(rang[k]<rang[p])
    {
        t[k]=p;
    }
    else
        if(rang[k]>rang[p])
        {
             t[p]=k;
        }
        else
        {
            if(rang[k]==rang[p])
            {
                rang[k]++;
                t[p]=k;
            }
        }
}

void intializ_t()
{
    for(int i=1;i<=n;i++)
        t[i]=i;
}

void kruskal()
{
    int s=0,aj,ai,l=0;
    for(int i=1;i<=m;i++)
        {
            if(radacina(x[i].i)!=radacina(x[i].j))
               {
                    ranguri(radacina(x[i].i),radacina(x[i].j));
                    s+=x[i].cost;
                    l++;
                    x[i].ok=1;

               }

        }
    g<<s<<'\n'<<l<<'\n';
    for(int i=1;i<=l;i++)
       if(x[i].ok==1)
         g<<x[i].j<<" "<<x[i].i<<'\n';
}

int pivot(int s,int d)
{
    int i=s,j=d,di=0,dj=1,aux;
    while(i<j)
    {
        if (x[i].cost>x[j].cost)
        {
            muchie aux;
            aux=x[j];
            x[j]=x[i];
            x[i]=aux;
        }
        i=i+di;
        j=j-dj;
    }
    return i;
}

void sortare(int s,int d)
{
    int p;
    if (s<d)
    {
        p=pivot(s,d);
        sortare(s,p-1);
        sortare(p+1,d);
    }
}


int main()
{
    citire();
    sortare(1,m);
    intializ_t();
    kruskal();
    return 0;
}