#include<stdio.h>
#include<algorithm>
#define MAXV 200000
#define MAXE 400000
struct Edge
{
    int src,dst,cost;
};
bool cmp(Edge a,Edge b);
int reprez(int x);
FILE*fin,*fout;
Edge edges[MAXE+1];
int id[MAXV+1];
int selected_muc[MAXE+1];
int ultmuc=0;
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<=V;i++)
    {
        id[i]=i;
    }
    for(int i=1;i<=E;i++)
    {
        fscanf(fin,"%d%d%d",&edges[i].src,&edges[i].dst,&edges[i].cost);
    }
    std::sort(edges+1,edges+E+1,cmp);
    long long ans=0;
    for(int i=1;i<=E;i++)
    {
        int boss1=reprez(edges[i].src);
        int boss2=reprez(edges[i].dst);
        if(boss1!=boss2)
        {
            id[boss1]=boss2;
            ans+=edges[i].cost;
            selected_muc[++ultmuc]=i;
        }
    }
    fprintf(fout,"%lld\n%d\n",ans,ultmuc);
    for(int i=1;i<=ultmuc;i++)
    {
        fprintf(fout,"%d %d\n",edges[selected_muc[i]].src,edges[selected_muc[i]].dst);
    }
}
bool cmp(Edge a,Edge b)
{
    return a.cost<b.cost;
}
int reprez(int x)
{
    if(x==id[x])
    {
        return x;
    }
    return id[x]=reprez(id[x]);
}