#include <cstdio>
#include <algorithm>
#define MAXN 200001
#define MAXM 400000
int nxt[MAXN],h[MAXN],sol[MAXN-2];
struct muchie
{
    int x,y,cost;
}v[MAXM];
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;
    }
}
inline bool cmp(muchie x,muchie y)
{
    return x.cost<y.cost;
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    int n,m,j,nod1,nod2,c=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);n--;j=0;
    for(int i=0;i<n;i++)
    {
        while((nod1=root(v[j].x))==(nod2=root(v[j].y)))
            j++;
        c+=v[j].cost;sol[i]=j;
        unite(nod1,nod2);j++;
    }
    fprintf(fout,"%d\n%d\n",c,n);
    for(int i=0;i<n;i++)
        fprintf(fout,"%d %d\n",v[sol[i]].x,v[sol[i]].y);
    fclose(fin);
    fclose(fout);
    return 0;
}