#include <cstdio>
#include <queue>

using namespace std;
int n,muchii,r1,r2,costmin,i,k,t[200005];
struct muchie
{
    int x,y,cost;
    friend bool operator>(const muchie&, const muchie&);
}m, solx[200005];

bool operator>(const muchie&m1, const muchie&m2)
{
    return m1.cost>m2.cost;
}

priority_queue<muchie, vector <muchie>, greater<muchie> >H;

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

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&muchii);
    for (i=1; i<=muchii; i++)
    {
        scanf("%d%d%d",&m.x,&m.y,&m.cost);
        H.push(m);
    }
    for (i=1; i<=n; i++)
        t[i]=i;
    while (k<n-1)
    {
        m=H.top();
        H.pop();
        r1=rad(m.x);
        r2=rad(m.y);
        if (r1!=r2)
        {
            k++;
            solx[k]=m;
            costmin=costmin+m.cost;
            t[r2]=r1;
        }
    }
    printf("%d\n%d\n",costmin,k);
    for (i=1; i<=k; i++)
        printf("%d %d\n",solx[i].x,solx[i].y);
    printf("\n");
    return 0;
}