#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define maxn 400003
int ind[maxn],x[maxn],y[maxn],dist[maxn];
int t[100003],rg[100003];
bool use[400003];
int n,m,i,xx,yy,op;

int father(int a)
{
    while(t[a])
        a=t[a];
    return a;
}
int tx,ty,cx;
bool cmp(int i,int j)
{
    return dist[i]<dist[j];
}
typedef long long ll;
long long cost,cate;
int main()
{
    f>>n;
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>x[i]>>y[i]>>dist[i];
        ind[i]=i;
    }
    sort(ind+1,ind+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        xx=x[ind[i]];
        yy=y[ind[i]];
        tx=father(xx);
        ty=father(yy);
        if(tx!=ty)
        {
            use[i]=1;
            cate+=1;
            cost+=ll(dist[ind[i]]);
            while(t[xx])
            {
                cx=xx;
                xx=t[xx];
                t[cx]=tx;
            }
            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<<x[i]<<" "<<y[i]<<'\n';
    return 0;
}