#include <cstdio>
#include <algorithm>
using namespace std;
struct muchie{int a;int b;int cost;};
struct muchie2{int a;int b;};
muchie v[400002];
muchie2 sol[200002];
int tata[200002],niv[200002];
int myfind(int a)
{
    int ok=1;
    while(ok)
        if(tata[a])
            a=tata[a];
        else ok=0;
    return a;
}
void myunion(int t1,int t2)
{
    if(niv[t1]<niv[t2])
        tata[t1]=t2;
    else if(niv[t1]>niv[t2])
        tata[t2]=t1;
    else tata[t1]=t2,niv[t2]++;
}
int cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,s=0,k=0,x,y,t1,t2;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&v[i].a,&v[i].b,&v[i].cost);
    sort(&v[1],&v[m+1],cmp);
    for(i=1;i<=m&&k<n-1;i++)
    {
        x=v[i].a;
        y=v[i].b;
        t1=myfind(x);
        t2=myfind(y);
        if(t1!=t2)
        {
            k++;
            sol[k].a=x;
            sol[k].b=y;
            s+=v[i].cost;
            myunion(t1,t2);
        }
    }
    printf("%d\n%d\n",s,k);
    for(i=1;i<=k;i++)
        printf("%d %d\n",sol[i].a,sol[i].b);

    return 0;
}