#include<cstdio>
#include<algorithm>

using namespace std;

int n,m,c;
int tata[200010],sz[200010];
int res[400010],lim,cost;

struct str
{
    int n1;
    int n2;
    int c;
}a[400010];

int comp(str a,str b)
{
    return a.c<b.c;
}

int exista(int n1,int n2)
{
    while(tata[n1]!=n1)
    {
        n1=tata[n1];
    }
    while(tata[n2]!=n2)
    {
        n2=tata[n2];
    }

    if(n1==n2)
    {
        return 1;
    }
    return 0;
}

int leaga(int n1,int n2)
{
    int t1=n1,t2=n2;

    while(tata[t1]!=t1)
    {
        t1=tata[t1];
    }
    while(tata[t2]!=t2)
    {
        t2=tata[t2];
    }

    if(sz[t1]>sz[t2])
    {
        tata[t2]=t1;
        sz[t1]=max(sz[t1],sz[t2]+sz[n1]);
    }
    else
    {
        tata[t1]=t2;
        sz[t2]=max(sz[t2],sz[t1]+sz[n2]);
    }
}

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

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

    for(int i=1;i<=n;i++)
    {
        sz[i]=1;
        tata[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a[i].n1,&a[i].n2,&a[i].c);
    }

    sort(a+1,a+m+1,comp);

    for(int i=1;i<=m;i++)
    {
        if(exista(a[i].n1,a[i].n2)==0)
        {
            cost+=a[i].c;
            lim++;
            res[lim]=i;
            leaga(a[i].n1,a[i].n2);
        }
    }
    printf("%d\n%d\n",cost,lim);
    for(int i=1;i<=lim;i++)
    {
        printf("%d %d\n",a[res[i]].n1,a[res[i]].n2);
    }
}