#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX=400000;

struct MUCHIE
{
    int u,v,cost,sel;
};
MUCHIE vv[NMAX+5];
int t[200005],h[200005];
bool cmp(MUCHIE a,MUCHIE b)
    {
        return a.cost<b.cost;
    }
int FindSet(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
void UnionSet(int x,int y)
{
    if(h[x]==h[y])
    {
        h[x]++;
        t[y]=x;
    }
    else
        if(h[x]<h[y])
            t[x]=y;
        else
            t[y]=x;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,n,m,u,v,tv,tu,totalc,ma,x,y,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        vv[i].u=x;
        vv[i].v=y;
        vv[i].cost=c;
    }
    sort(vv+1,vv+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        h[i]=1;
        t[i]=i;
    }
    ma=0;
    totalc=0;
    for(i=1;i<=m&&ma<n-1;i++)
    {
        tu=FindSet(vv[i].u);
        tv=FindSet(vv[i].v);
        if(tu!=tv)
        {
            ma++;
            vv[i].sel=1;
            totalc+=vv[i].cost;
            UnionSet(tu,tv);
        }
    }
    printf("%d\n",totalc);
    printf("%d\n",n-1);
    for(i=1;i<=m;i++)
        if(vv[i].sel==1)
            printf("%d %d\n",vv[i].v,vv[i].u);
    return 0;
}