#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
int x,y,c;
};muchie v[400001],sol[400001];
int sef[200001];
int boss(int x)
{
    if(sef[x]==x)
        return x;
    else
        return sef[x]=boss(sef[x]);
}
void unire(int x,int y)
{
    int sef_x=boss(x);
    int sef_y=boss(y);
    sef[sef_y]=sef_x;
}
bool cmp(muchie a,muchie b){
    if(a.c<b.c)
        return true;
    return false;
}
int main()
{
    int N,M,s,k;
    s=0; k=0;
    f>>N>>M;
    for(int i=1;i<=M;++i)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+M+1,cmp);
    for(int i=1;i<=N;++i)
        sef[i]=i;
    for(int i=1;i<=M;++i){
        if(boss(v[i].x)!=boss(v[i].y))
        {
            s+=v[i].c;
            unire(v[i].x,v[i].y);
            k++;
            sol[k]=v[i];
        }
    }
    g<<s<<endl<<k<<endl;
    for(int i=1;i<=k;++i)
            g<<sol[i].x<<" "<<sol[i].y<<endl;
    f.close();
    g.close();
    return 0;

}