#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
pair <int, pair <int, int> > a[400004];
pair <int, int> v[400004];
int i,n,m,p[200004],r[200004],x,y,s,x1,y2,nr;
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf ("%d %d", &n, &m);
    for (i=1;i<=m;i++)
        scanf ("%d %d %d", &a[i].second.first, &a[i].second.second, &a[i].first);
    sort (a+1,a+m+1);
    for (i=1;i<=n;i++)
    {
        p[i]=i;
        r[i]=1;
    }
    for (i=1;i<=m;i++)
    {
        x=a[i].second.first;
        y=a[i].second.second;
        x1=x;
        y2=y;
        while (p[x1]!=x1)
            x1=p[x1];
        while (p[y2]!=y2)
            y2=p[y2];
        if (x1!=y2)
        {
            s+=a[i].first;
            v[++nr].first=x;
            v[nr].second=y;
            if (r[x1]>r[y2])
                p[y2]=x1;
            else if (r[x1]<r[y2])
                p[x1]=y2;
            else
            {
                p[y2]=x;
                r[x1]++;
            }
        }
    }
    printf ("%d\n", s);
    printf ("%d\n", nr);
    for (i=1;i<=nr;i++)
        printf ("%d %d\n", v[i].first, v[i].second);
    return 0;
}