#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX=400005;

struct muchie
{
    int x,y,c;
} v[NMAX],sol[NMAX];

int tata[NMAX],h[NMAX];

bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}

int find1(int x)
{
    if(x==tata[x]) return x;

    tata[x]=find1(tata[x]);
    return tata[x];
}

void union1(int a,int b)
{
    if(h[a]<h[b]) tata[a]=b;
    else
    {
        tata[b]=a;
        if(h[a]==h[b]) h[a]++;
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int n,m,i,a,b,sum=0,cnt=0;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++) scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    for(i=1;i<=m;i++) tata[i]=i;

    sort(&v[1],&v[m+1],cmp);

    for(i=1;i<=m;i++)
    {
        if(cnt==n-1) break;

        a=find1(v[i].x);
        b=find1(v[i].y);

        if(a!=b)
        {
            cnt++;
            sum+=v[i].c;
            sol[cnt]=v[cnt];

            union1(a,b);
        }
    }

    printf("%d\n%d\n",sum,cnt);

    for(i=1;i<=cnt;i++) printf("%d %d\n",sol[i].x,sol[i].y);

    return 0;
}