#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
    int x, y, cost;
    int viz=0;
} muc[200001];

int n, m;
int a[200001], b[200001];

void init()
{
    for (int i=1; i<=n; i++)
    {
        a[i]=i;
        b[i]=1;
    }
}

int caut(int x)
{
    int r=x;

    while (a[x]!=x)
        x=a[x];

    while (r!=x)
    {
        int next=a[r];
        a[r]=x;
        r=next;
    }

    return x;
}

void reun(int x, int y)
{
    int ty=caut(y);
    int tx=caut(x);
    if (b[ty]<b[tx])
    {
        a[ty]=tx;
        b[ty]=b[tx];
    }
    else if (b[tx]<b[ty])
    {
        a[tx]=ty;
        b[tx]=b[ty];
    }
    else
    {
        a[tx]=ty;
        b[ty]++;
        b[tx]=b[ty];
    }
}

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

void cit()
{
    f>>n>>m;

    for (int i=0; i<m; i++)
        f>>muc[i].x>>muc[i].y>>muc[i].cost;
}

int krusk()
{
    int c=0;

    for (int i=0; i<m; i++)
    {
        if (caut(muc[i].x)!=caut(muc[i].y))
        {
            muc[i].viz=1;
            c+=muc[i].cost;

            reun(muc[i].x, muc[i].y);
        }
    }

    return c;
}

void afis()
{
    g<<krusk()<<'\n'<<n-1<<'\n';

    for (int i=0; i<m; i++)
        if (muc[i].viz)
            g<<muc[i].x<<' '<<muc[i].y<<'\n';
}

int main()
{
    cit();

    init();
    sort(muc, muc+m, cmp);

    afis();

    return 0;
}