#include <fstream>
#define N  200002
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int tata[N],rang[N];
struct bla
{
    int a,b,c;
}arb[N];
struct bla1
{
    int x,y;
}sol[N];
bool cmp(bla A, bla B)
{
    return (A.c<B.c);
}
int root(int nod)
{
    while(nod!=tata[nod])
        nod=tata[nod];
    return nod;
}
void unite(int ra, int rb)
{
    if(rang[ra]<rang[rb])
        tata[ra]=tata[rb];
    else
        tata[rb]=tata[ra];
    if(rang[ra]==rang[rb])
        ++rang[ra];
}
int main()
{
    int n,m,ss=0,nr=0,ra,rb;
    f>>n>>m;
    for(int i=1;i<=m;++i)
        f>>arb[i].a>>arb[i].b>>arb[i].c;
    for(int i=1;i<=n;++i) tata[i]=i;
    sort(arb+1,arb+m+1,cmp);
    for(int i=1;i<=m;++i)
    {
        ra=root(arb[i].a);
        rb=root(arb[i].b);
        if(ra!=rb)
        {
            ss+=arb[i].c;
            ++nr;
            sol[nr]={arb[i].a,arb[i].b};
            unite(ra,rb);
        }
    }
    g<<ss<<'\n'<<nr<<'\n';
    for(int i=1;i<=nr;++i)
        g<<sol[i].x<<' '<<sol[i].y<<'\n';
    f.close();
    g.close();
    return 0;
}