#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

struct muchie{
    int x,y,cost;
    bool in_ama;
};

struct submult
{
    int p;
    int nivel;
};

bool compar (muchie m1, muchie m2)
{
    return m1.cost < m2.cost;
}

int cauta (submult submultimi[], int v)
{
    if (submultimi[v].p != v)
        return cauta(submultimi, submultimi[v].p);

    return submultimi[v].p;
}

int uniune(submult submultimi[], int u, int v)
{
    int radu = cauta(submultimi, u);
    int radv = cauta(submultimi, v);

    if (radu == radv)
        return 0;

    if (submultimi[radu].nivel < submultimi[radv].nivel)
        submultimi[radu].p = radv;
    else
        if (submultimi[radu].nivel > submultimi[radv].nivel)
            submultimi[radv].p = radu;

    else
    {
        submultimi[radv].p = radu;
        submultimi[radu].nivel++;
    }

    return 69;
}

submult submultimi[200001];

int main()
{
    fstream f("apm.in",ios::in);
    fstream out("apm.out",ios::out);
    vector<muchie> u;
    int n,m,i,ma,costot=0,j,arbtemp,x,y,cost;


    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        muchie m;
        m.x=x;
        m.y=y;
        m.cost=cost;
        m.in_ama = false;

        u.push_back(m);
    }
    sort(u.begin(), u.end(), compar);

    for(i=1;i<=n;i++)
        submultimi[i].p = i;

    ma=0;
    i=0;

    for(i=0;i<m;i++)
    {
        if (uniune(submultimi, u[i].x, u[i].y))
        {
            ma++;
            costot += u[i].cost;

            u[i].in_ama = true;
        }

        if(ma == n-1)
            break;
    }

    out<<costot<<endl<<n-1<<endl;

    for(i=0;i<m;i++)
        if(u[i].in_ama)
            out<<u[i].x<<" "<<u[i].y<<endl;

    return 0;
}