#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
pair <int, pair <int, int> > a[400004];
vector <pair <int, int> > v;
int i,n,m,p[200004],r[200004],x,y,s;
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;
        while (p[x]!=x)
            x=p[x];
        while (p[y]!=y)
            y=p[y];
        if (x!=y)
        {
            s+=a[i].first;
            v.push_back(pair<int,int> (x, y));
            if (r[x]>r[y])
                p[y]=x;
            else if (r[x]<r[y])
                p[x]=y;
            else
            {
                p[y]=x;
                r[x]++;
            }
        }
    }
    printf ("%d\n", s);
    printf ("%d\n", v.size());
    for (i=0;i<=(v.size()-1);i++)
        printf ("%d %d\n", v[i].first, v[i].second);
    return 0;
}