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

int crt(muchii a,muchii b)
{
    return a.cost<b.cost;
}

void unire(int x, int y)
{
    if(rang[x]<rang[y])
    {
        t[x]=t[y];
    }
    else
    {
        t[y]=t[x];
        if(rang[x]==rang[y])
        {
            rang[y]++;
        }
    }
}

int radacina(int k)
{
    if(k!=t[k])
        k=radacina(t[k]);
    return 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';
}

int main()
{
    citire();
    sort(x+1,x+m+1,crt);
    intializ_t();
    kruskal();
    return 0;
}