#include<fstream>
#include<algorithm>
using namespace std;
ifstream W("apm.in");
ofstream Z("apm.out");
struct g {
    int x,y,c;
}v[200001];
int p[400001],t[400001],r,s,n,m,i;
bool C(g i,g j)
{
    return i.c<j.c;
}
int G(int x)
{
    return t[x]==x?x:(t[x]=G(t[x]));
}
void U(int x,int y)
{
    t[G(x)]=G(y);
}
int main()
{
    W>>n>>m;
    for(i=1;i<=m;++i)
        W>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,C);
    for(i=1;i<=n;++i)
        t[i]=i;
    for(i=1;i<=m;++i)
        if(G(v[i].x)!=G(v[i].y))
            p[++r]=i,s+=v[i].c,U(v[i].x,v[i].y);
    Z<<s<<'\n'<<r<<'\n';
    for(i=1;i<=r;++i)
        Z<<v[p[i]].x<<' '<<v[p[i]].y<<'\n';
    return 0;
}