#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

int rang[100001],t[100001],costtotal,n,m,nrm;

struct muchii{
    int i,j,cost;
}x[120001],aux,v[100001];

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

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

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

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

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

void kruskal()
{
    int tata1,tata2,l=0,cost=0;

    for(int i=1;i<=m;i++)
    {
        tata1=radacina(x[i].i);
        tata2=radacina(x[i].j);
        if(tata1!=tata2)
        {
            cost+=x[i].cost;
            ranguri(tata1,tata2);
            v[++l].i=x[i].i;
            v[l].j=x[i].j;
        }
    }
    g<<cost<<'\n'<<l<<'\n';
    for(int i=1;i<=l;i++)
        g<<v[i].i<<" "<<v[i].j<<'\n';
}

int main()
{

    citire();
    initializ_t();
    sort(x+1,x+m+1,crit);
    kruskal();

    return 0;
}