#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct nod
{
    int x,y,dist;
};
nod v[400003];
int t[100003],rg[100003];
bool use[400003];
int n,m,i,x,y,dist;
bool cmp(nod a,nod b)
{
    if(a.dist>b.dist)
        return 0;
    return 1;
}
int father(int a)
{
    while(t[a])
        a=t[a];
    return a;
}
int tx,ty,cx;
typedef long long ll;
long long cost,cate;
int main()
{
    f>>n;
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].dist;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        tx=father(v[i].x);
        ty=father(v[i].y);
        if(tx!=ty)
        {
            use[i]=1;
            cate+=1;
            cost+=ll(v[i].dist);
            while(t[x])
            {
                cx=t[x];
                t[x]=tx;
                x=cx;
            }
            if(rg[tx]==rg[ty])
            {
                rg[tx]+=1;
                t[ty]=tx;
            }
            else
                if(rg[tx]>rg[ty])
                    t[ty]=tx;
                else
                    t[tx]=ty;
        }
    }
    g<<cost<<'\n'<<cate<<'\n';
    for(i=1;i<=m;i++)
        if(use[i]==1)
            g<<v[i].x<<" "<<v[i].y<<'\n';
    return 0;
}