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

using namespace std;

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

struct muchie{
    int i,j,cost;
}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;
                    v[++l].i=x[i].i;
                    v[l].j=x[i].j;

               }

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

void ordonare()
{
    for(int i=1;i<m;i++)
        for(int j=i+1;j<=m;j++)
            if(x[i].cost>x[j].cost)
                {
                    muchie aux;
                    aux=x[j];
                    x[j]=x[i];
                    x[i]=aux;
                }
}

int main()
{
    citire();
    ordonare();
    intializ_t();
    kruskal();
    return 0;
}