#include <cstdio>
#include<algorithm>
using namespace std;
struct apm
{
    int x,y,c;
};
apm v[400005];
int t[200005];
int h[200005];
int findset(int x)
{
    while(t[x]!=x)
        x=t[x];
    return x;
}
bool unionset(int x,int y)
{
    int tx,ty;
    tx=findset(x);
    ty=findset(y);
    if(tx==ty)
        return 0;
    if(h[tx]==h[ty])
    {
        h[tx]++;
        t[ty]=t[tx];
    }
    else
        if(h[tx]<h[ty])
            t[tx]=t[ty];
        else
            t[ty]=t[tx];
    return 1;

}
bool cmp(apm a,apm b)
{
    if(a.c==b.c)
        return a.x<b.x;

    return a.c<b.c;
}
int main()

{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int cost=0,n,m,i,j,nr=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);
    sort(v+1,v+m+1,cmp);
    for(i=1; i<=n; i++)
        t[i]=i;
    for(i=1; i<=m && nr<=n-1; i++)
    {
        if(unionset(v[i].x,v[i].y))
            cost+=v[i].c,nr++,v[i].c=1005;
    }
    printf("%d\n%d\n",cost,n-1);
    for(j=1; j<=i; j++)
        if(v[j].c==1005)
        printf("%d %d\n",v[j].x,v[j].y);
    return 0;
}