#include <fstream>
#include <algorithm>

using namespace std;

int N,M,cost_minim,len,a[200005],b[200005],t[200005];

struct muchie
{
    int X,Y,cost;
    bool operator <(const muchie &A) const
    {
        return cost<A.cost;
    }
};
muchie v[400005];

inline void Read()
{
    int i;
    ifstream fin("apm.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
        fin>>v[i].X>>v[i].Y>>v[i].cost;
    fin.close();
}

inline int Find(int a)
{
    int i=a,rad;
    while(t[a]>0)
        a=t[a];
    rad=a;
    while(t[i]>0)
    {
        a=i;
        i=t[i];
        t[a]=rad;
    }
    return rad;
}

inline void Union(int a, int b)
{
    t[a]+=t[b];
    t[b]=a;
}

inline void Solve()
{
    int i,x,y,radx,rady;
    sort(v+1,v+M+1);

    for(i=1;i<=N;i++)
        t[i]=-1;

    for(i=1;i<=M;i++)
    {
        x=v[i].X; y=v[i].Y;
        radx=Find(x); rady=Find(y);
        if(radx!=rady)
        {
            cost_minim+=v[i].cost;
            len++;
            a[len]=x; b[len]=y;
            Union(radx,rady);
        }
    }

    ofstream fout("apm.out");
    fout<<cost_minim<<"\n"<<len<<"\n";
    for(i=1;i<=len;i++)
        fout<<a[i]<<" "<<b[i]<<"\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}