#include <cstdio>
#include <algorithm>
const int Maxm=400000;
const int Maxn=200000;
struct elem
{
    int x,y;
}sol[Maxn-1];
struct muchie
{
    int x,y,cost;
}v[Maxm];
int nxt[Maxn],h[Maxn];
inline bool cmp(muchie x,muchie y)
{
    return x.cost<y.cost;
}
int root(int x)
{
    if(nxt[x])
        return nxt[x]=root(nxt[x]);
    return x;
}
inline void unite(int x,int y)
{
    if(h[x]<h[y])
        nxt[x]=y;
    else
    {
        if(h[x]==h[y])
            h[x]++;
        nxt[y]=x;
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    int n,m,s=0,j=0;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=0;i<m;i++)
        fscanf(fin,"%d%d%d",&v[i].x,&v[i].y,&v[i].cost);
    std::sort(v,v+m,cmp);
    for(int i=1;i<n;i++)
    {
        while(root(v[j].x)==root(v[j].y))
            j++;
        s+=v[j].cost;
        sol[i-1].x=v[j].x;sol[i-1].y=v[j].y;
        unite(root(v[j].x),root(v[j].y));
        j++;
    }
    fprintf(fout,"%d\n%d\n",s,n-1);
    for(int i=0;i<n-1;i++)
        fprintf(fout,"%d %d\n",sol[i].x,sol[i].y);
    fclose(fin);
    fclose(fout);
    return 0;
}