#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int vec;
    int cost;
};

struct nod
{
    vector <muchie> v;
};

struct muchie0
{
    int x;
    int y;
};
struct muchie1
{
    int x;
    int y;
    int cost;
};

int t[200003];
int r[200003];

int radacina(int x)
{
    int rad=x;

    while(t[x]!=x)
    {
        rad=t[x];
        x=t[x];
    }

    int temp;

    while(t[x]!=x)
    {
        temp=t[x];

        t[x]=rad;

        x=temp;
    }

    return rad;
}

void uneste(int x, int y)
{
    int radx=radacina(x);
    int rady=radacina(y);

    if(r[radx] < r[rady])
        t[radx]=rady;
    else
        t[rady]=radx;

    if(r[radx]==r[rady])
        r[radx]++;
}

nod g[200001];
int n, m;

vector <muchie0> a;
vector <muchie1> gra;

bool myf(muchie1 x, muchie1 y)
{
    return x.cost < y.cost;
}

int main()
{
    fin >> n >> m;

    for(int i=1; i<=m; i++)
    {
        int x, y, cost;
        muchie p;

        fin >> x >> y >> cost;

        p.cost=cost;
        p.vec=y;

        g[x].v.push_back(p);

        p.vec=x;

        g[y].v.push_back(p);

        muchie1 ed;
        ed.x=x;
        ed.y=y;
        ed.cost=cost;

        gra.push_back(ed);
    }

    sort(gra.begin(), gra.end(), myf);

    for(int i=1; i<=n; i++)
    {
        t[i]=i;
        r[i]=1;
    }

    int ctot=0;

    for(int i=0; i<=m; i++)
    {
        int vmin;

        muchie0 ctm;

        ctm.x=gra[i].x;
        ctm.y=gra[i].y;

        if(radacina(gra[i].x)!=radacina(gra[i].y))
        {
            ctot+=gra[i].cost;
            a.push_back(ctm);
            uneste(gra[i].x, gra[i].y);
        }
    }

    fout << ctot << '\n';
    fout << a.size() << '\n';

    for(int i=0; i<a.size(); i++)
        fout << a[i].x << " " << a[i].y << '\n';

    return 0;
}