#include <fstream>
#include <algorithm>

using namespace std;

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

int sef[200003];

struct Muchie
{
    int x, y, cost;
};

Muchie v[400003];
int sol[400003];

int sef_sup(int nod)
{
    if(sef[nod]==nod) return nod;
    return sef[nod]=sef_sup(sef[nod]);
}

void unire(int x, int y)
{
    int sefx=sef_sup(x);
    int sefy=sef_sup(y);
    sef[sefx]=sefy;
}

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

int main()
{
    int n, m, i, nr=0, cost_min=0;
    cin>>n>>m;

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

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

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

    for(i=1;i<=m;i++)
    {
        int x=v[i].x;
        int y=v[i].y;

        if(sef_sup(x)!=sef_sup(y))
        {
            unire(x,y);
            cost_min+=v[i].cost;
            sol[++nr]=i;

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

    cout<<cost_min<<'\n';
    cout<<nr<<'\n';

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

    return 0;
}