#include <cstdio>
#include <algorithm>

using namespace std;

struct edge
{
    int x,y,cost;
};

edge v[400010],v1[200010];
int rad[200010];

int cmp(edge a,edge b)
{
    return a.cost<b.cost;
}

int radacina(int x)
{
    int y=x;
    while(rad[y]!=y) y=rad[y];
    while(x!=y)
    {
        int aux=rad[x];
        rad[x]=y;
        x=aux;
    }
    return y;
}

void reuneste(int x,int y)
{
    int a=radacina(x),b=radacina(y);
    rad[a]=b;
}

int query(int x,int y)
{
    int a=radacina(x);
    int b=radacina(y);
    if(a!=b) return 1;
    else return 0;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,r=0,l=0,x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[i].x=x;v[i].y=y;v[i].cost=c;
    }
    for(int i=1;i<=n;i++)
        rad[i]=i;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(query(v[i].x,v[i].y)==1)
        {
            l++;
            v1[l].x=v[i].x;
            v1[l].y=v[i].y;
            r=r+v[i].cost;
            reuneste(v[i].x,v[i].y);
        }
        if(l==n-1) break;
    }
    printf("%d\n",r);
    printf("%d\n",l);
    for(int i=1;i<=l;i++)
        printf("%d %d\n",v1[i].x,v1[i].y);
    return 0;
}