#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,i,cost,t[200001],h[200001],a,b,x[400001],y[400001],c[400001],o[400001];
vector<pair<int,int> > r;
bool cmp(int a,int b)
{
    return c[a]<c[b];
}
int arb(int n)
{
    while (t[n]) n=t[n];
    return n;
}
void kruskal()
{
    int i,j=0;
    for (i=1;i<n;i++)
    {
        while (true)
        {
            j++;
            a=arb(x[o[j]]);
            b=arb(y[o[j]]);
            if (a!=b) break;
        }
        r.push_back(make_pair(x[o[j]],y[o[j]]));
        cost+=c[o[j]];

        if (h[a]>h[b]) t[b]=a;
        else if (h[a]<h[b]) t[a]=b;
        else
        {
            h[a]++;
            t[b]=a;
        }
    }
}
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%i%i%i",&x[i],&y[i],&c[i]);
        o[i]=i;
    }

    sort(o+1,o+m+1,cmp);

    kruskal();

    printf("%i\n%i\n",cost,n-1);
    for (i=0;i<r.size();i++)
        printf("%i %i\n",r[i].first,r[i].second);
    fclose(stdin);
    fclose(stdout);
    return 0;
}