#include<cstdio>
#include<algorithm>

using namespace std;

const int nmax=200005;

struct muchie
{
    int a,b,cost;
};
muchie g[2*nmax];
int n,m,t[nmax],h[nmax],a[nmax];

inline int findset(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}

inline void unionset(int a,int b)
{
    if(h[a]>h[b])
    {
        t[b]=a;
        h[a]+=h[b];
    }
    else
    {
        t[a]=b;
        h[b]+=h[a];
    }
}

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

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int cnt=0,i,j,s=0,ta,tb;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&g[i].a,&g[i].b,&g[i].cost);
    for(i=1;i<=n;++i)
        t[i]=i,h[i]=1;
    sort(g+1,g+m+1,cmp);
    for(i=1;cnt<n-1;++i)
    {
        ta=findset(g[i].a);
        tb=findset(g[i].b);
        if(ta!=tb)
        {
            a[++cnt]=i;
            unionset(findset(g[i].a),findset(g[i].b));
            s+=g[i].cost;
        }
    }
    printf("%d\n",s);
    printf("%d\n",cnt);
    for(i=1;i<=cnt;i++)
        printf("%d %d\n",g[a[i]].a,g[a[i]].b);
}