#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin ("apm.in");
ofstream cout ("apm.out");

struct ura {
    int x,y,cost;
} v[400003],sol[200001];

int tata[200001];

bool sor(ura a,ura b)
{
    if (a.cost!=b.cost)
        return a.cost<b.cost;
    if (a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}

int radacina(int x)
{
    if (tata[x]==x)
        return x;
    return tata[x]=radacina(tata[x]);
}

int main()
{
    int n,m,i,x,y,rx,ry;
    int total=0,nr=0;

    cin >> n >> m;

    for (i=1;i<=m;i++)
        cin >> v[i].x >> v[i].y >> v[i].cost;

    sort(v+1,v+m+1,sor);

    for (i=1;i<=n;i++)
        tata[i]=i;

    for (i=1;i<=m && nr<n-1;i++)
    {
        x=v[i].x;
        y=v[i].y;

        rx=radacina(x);
        ry=radacina(y);

        if (rx!=ry)
        {
            tata[rx]=ry;
            sol[++nr]=v[i];
            total+=v[i].cost;
        }
    }

    cout << total << '\n' << nr << '\n';

    for (i=1;i<=nr;i++)
        cout << sol[i].x << " " << sol[i].y << '\n';

    return 0;
}