#include<fstream>
#include<algorithm>
#define nmax 200001
#define mmax 400001
using namespace std;

struct muchie{
    int x,y,cost;
};

muchie IN[mmax],Rez[mmax];
int kR,costmin;
int T[nmax],H[nmax];
int N,M;


bool comp(muchie a,muchie b)
{
    if(a.cost<b.cost)
    return true;
    return false;
}
//Proceduri multimi

int reprez(int x)
{
    int rad=x,t,y;
    while(T[rad]!=0)
    rad=T[rad];

    y=x;
    t=T[x];
    while(y!=rad)
    {
        t=T[y];
        T[y]=rad;
        y=t;
    }

    return rad;
}

void uneste(int x,int y)
{
    int radx,rady;
    radx=reprez(x);
    rady=reprez(y);

    if(radx!=rady)
    {
        if(H[radx]>H[rady])
         T[rady]=radx;
         else
         {
             T[radx]=rady;
             if(H[radx]==H[rady])
             ++H[rady];
         }
    }
}

void citeste()
{
    ifstream f("apm.in");
    int i;

    f>>N>>M;
    for(i=1;i<=M;i++)
    f>>IN[i].x>>IN[i].y>>IN[i].cost;

    f.close();
}

void Kruskal()
{
    int i,x,y;

    sort(IN+1,IN+M+1,comp);

    for(i=1;i<=M;i++)
    {
        x=IN[i].x;
        y=IN[i].y;
        if(reprez(x)!=reprez(y))
        {
            uneste(x,y);
            Rez[++kR]=IN[i];
            costmin+=IN[i].cost;
        }
    }
}

void rezolva()
{
    Kruskal();
}

void scrie()
{
    ofstream g("apm.out");
    int i;

    g<<costmin<<'\n'<<kR<<'\n';
    for(i=1;i<=kR;i++)
    g<<Rez[i].x<<' '<<Rez[i].y<<'\n';

    g.close();
}

int main()
{
    citeste();
    rezolva();
    scrie();
    return 0;
}