#include <algorithm>
#include <cstdio>

using namespace std;

struct muchie{
    int x,y,cost;
}e[400002],apm[200002];
int tata[200002],nr[200002];

bool cmp(muchie x,muchie y)
{
    return x.cost<y.cost;
}
int myfind(int x)
{
    int r=x,y;
    while(tata[r]!=0) r=tata[r];
    if(tata[x]!=0) while(tata[x]!=r)
    {
        y=tata[x];
        tata[x]=r;
        x=y;
    }
    return r;
}

void myunion(int a, int b)
{

        if(nr[a]<nr[b])tata[a]=b;
        else if(nr[a]>nr[b])tata[b]=a;
            else if(nr[a]==nr[b])
            {
                tata[a]=b;
                nr[b]++;
            }

}


int main()
{
    int n,m,i,s=0,a,b,x,y;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].cost);
    sort(e+1,e+m+1,cmp);
    int cnt=0;
    for(i=1;i<=m;i++)
    {
        a=e[i].x;
        b=e[i].y;
        x=myfind(a);
        y=myfind(b);
        if(x!=y)
        {
            cnt++;
            apm[cnt]=e[i];
            s=s+e[i].cost;
            myunion(x,y);
            if(cnt==n-1)
                break;
        }
    }
    printf("%d\n%d\n",s,cnt);
    for(i=1;i<=cnt;i++)
        printf("%d %d\n",apm[i].x,apm[i].y);

    return 0;
}