//KRUSKAL IMPLEMENTATION
//INITIERE PROCEDURA DE DOPAJ
#include<stdio.h>
#include<algorithm>
#define MAXV 200000
#define MAXE 400000
struct Edge
{
    int src,dst,cost;
};
bool cmp(Edge,Edge);
int reprez(int x);
void init();
FILE*fin,*fout;
Edge edges[MAXE+1];
int id[MAXE+1];
int sol[MAXE+1];
int V,E;
int main()
{
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    fscanf(fin,"%d%d",&V,&E);
    for(int i=1;i<=E;i++)
    {
        fscanf(fin,"%d%d%d",&edges[i].src,&edges[i].dst,&edges[i].cost);
    }
    init();
    std::sort(&edges[1],&edges[E+1],cmp);
    int nrsol=0;
    int totalCost=0;
    for(int i=1;i<=E;i++)
    {
        int boss1=reprez(edges[i].src);
        int boss2=reprez(edges[i].dst);
        if(boss1!=boss2)
        {
            sol[++nrsol]=i;
            totalCost+=edges[i].cost;
            id[boss1]=boss2;
        }
    }
    fprintf(fout,"%d\n%d\n",totalCost,nrsol);
    for(int i=1;i<=nrsol;i++)
    {
        fprintf(fout,"%d %d\n",edges[sol[i]].src,edges[sol[i]].dst);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}
bool cmp(Edge x,Edge y)
{
    return x.cost<y.cost;
}
int reprez(int x)
{
    if(x==id[x])
    {
        return x;
    }
    return id[x]=reprez(id[x]);

}
void init()
{
    for(int i=1;i<=E;i++)
    {
        id[i]=i;
    }
}