#include <bits/stdc++.h>
// 200002
using namespace std;

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

struct esol
{
    int a,b;
};

int n, i, j, m, sol, nre, t[200002];
muchie el;
vector<muchie>L;
esol q[200002];

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

int cmp(const muchie A, const muchie B)
{
    return A.c > B.c;
}
int Find(int x)
{
    int y,z;
    y=x;
    while(t[x]!=0)
        x=t[x];
    while(y!=x)
    {
        z=t[y];
        t[y]=x;
        y=z;
    }
    return x;
}
void Union(int x, int y)
{
    int rx=Find(x),ry=Find(y);
    t[rx] = ry;
}
void Citire()
{
    fin>>n>>m;
    for (i=1; i<=m;++i)
    {
        fin>>el.x;
        fin>>el.y;
        fin>>el.c;
        L.push_back(el);
    }
}
void Solutie()
{
    int rx, ry,i;
    sort(L.begin(),L.end(),cmp);
    i=1;
    while (i<=m)
    {
        el=L.back();
        rx=Find(el.x);
        ry=Find(el.y);
        if(rx!=ry)
        {
            Union(el.x, el.y);
            sol += el.c;
            q[++ nre].a = el.x;
            q[nre].b = el.y;
        }
        L.pop_back();
        ++i;
    }
}
void Afisare()
{
    fout<<sol<<"\n"<<nre<<"\n";
    for (i=1;i<=nre;++i)
        fout<<q[i].a<<" "<<q[i].b<<"\n";
}
int main()
{
    Citire();
    Solutie();
    Afisare();
    return 0;
}