#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

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

int n,M,i,j,x1,y2,c1,cost,rez,k,nr,q, t[200001], rang[200001], sol[400001][2];
bool ok[200001];

struct costuri{
    int x,y,c;
};

costuri m[400001];

bool cmp(costuri a, costuri b)
{
    return a.c < b.c;
}

int multime(int nod)
{
    if(t[nod]!=nod)
        t[nod]=multime(t[nod]);

    return t[nod];
}

void reun(int i,int j)
{
    i = multime(i);
    j = multime(j);

    if(i == j)
        return;
    if(rang[i]<rang[j])
        t[i] = j;
    else t[j] = i;

    if(rang[i] == rang[j])
        ++rang[i];
}

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

    for(i = 1; i <= M; ++i)
    {
        fin >> x1 >> y2 >> c1;
        m[i].x = x1;
        m[i].y = y2;
        m[i].c = c1;
    }

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

    for(i = 1; i <= n; ++i)
    {
        t[i] = i;
        rang[i] = 0;
    }

    memset(ok,0,sizeof(ok));

    q = 0;

    for(k = 1; k <= M; ++k)
    {
        i = m[k].x;
        j = m[k].y;
        cost = m[k].c;

        if(multime(i)!= multime(j))
        {
            reun(i,j);
            rez += cost;
            ++q;
            sol[q][0] = i;
            sol[q][1] = j;
        }
    }

    fout << rez << '\n' << q << '\n';

    for(i = 1; i <= q; ++i)
        fout << sol[i][0] << " " << sol[i][1] << '\n';

    return 0;
}