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

using namespace std;

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

int n,m,s=0,nr=0,ok[100002];

struct muchii
{
    int m1,m2,c;
};

muchii w[400002];

struct nocostm
{
    int m11,m22;
};

nocostm transition;

vector<int> v[100002];
vector<nocostm> sol;

bool condsort(muchii x, muchii y)
{
    if(x.c<y.c)
        return 1;
    return 0;
}

bool kkk=0;

void conexitate(int x, int y, int c)
{
    if(ok[x]==0 && ok[y]==0)
    {
        ok[x]=x;
        ok[y]=x;
        v[x].push_back(x);
        v[x].push_back(y);
        s+=c;
        nr++;
        kkk=1;
    }
    else
    {
        if(ok[x]!=0 && ok[y]==0)
        {
            ok[y]=ok[x];
            v[ok[x]].push_back(y);
            s+=c;
            nr++;
            kkk=1;
        }
        else
        {
            if(ok[x]==0 && ok[y]!=0)
            {
                ok[x]=ok[y];
                s+=c;
                nr++;
                kkk=1;
                v[ok[y]].push_back(x);
            }
            else
            {
                if(ok[x]!=0 && ok[y]!=0 && ok[y]!=ok[x])
                {
                    s+=c;
                    nr++;
                    kkk=1;
                    int ky;
                    ky=ok[y];
                    for(int i=0;i<v[ky].size();i++)
                    {
                        v[ok[x]].push_back(v[ky][i]);
                        ok[v[ky][i]]=ok[x];
                    }
                }
            }
        }
    }
    if(kkk==1)
        sol.push_back(transition);
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>w[i].m1>>w[i].m2>>w[i].c;

    sort(w+1,w+m+1,condsort);

    for(int i=1;i<=m;i++)
    {
        kkk=0;
        transition.m11=w[i].m2;
        transition.m22=w[i].m1;
        conexitate(w[i].m1,w[i].m2,w[i].c);
    }

    g<<s<<"\n"<<nr<<"\n";

    for(int i=0;i<sol.size();i++)
        g<<sol[i].m11<<" "<<sol[i].m22<<"\n";

    f.close();
    g.close();
    return 0;
}