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

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

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)
        submultimi[v].p = cauta(submultimi, submultimi[v].p);

    return submultimi[v].p;
}

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

    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++;
    }
}

submult submultimi[200001];

int main()
{
    fstream f("apm.in",ios::in);
    fstream out("apm.out",ios::out);
    vector<muchie> u;
    vector<muchie> rez;
    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;

        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++)
    {
        x = cauta(submultimi, u[i].x);
        y = cauta(submultimi, u[i].y);

        if (x != y)
        {
            ma++;
            muchie mu;
            mu.x=u[i].x;
            mu.y=u[i].y;
            costot += u[i].cost;

            rez.push_back(mu);

            uniune(submultimi, x, y);
        }
    }

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

    for(i=0;i<n-1;i++)
        out<<rez[i].x<<" "<<rez[i].y<<endl;
}