#include<fstream>
#include<algorithm>
using namespace std;
int n, m, i, rx, ry, cost, nrsol,                                                                                                                                              t[200005];
int rad(int x)
{
    int y=x, r;
    while(t[x]>0)
        x=t[x];
    r=x;
    x=y;
    while(t[x]>0)
    {
        y=t[x];
        t[x]=r;
        x=y;
    }
    return r;
}
ifstream in("apm.in");
ofstream out("apm.out");
struct x2
{
    int x;
    int y;
    int z;
};
x2 x[400005];
int cmp(x2 x, x2 y)
{
    return x.z<y.z;
}
                                                                                                                                                                pair<int, int> soll[200005];
int main()
{
    in>>n>>m;
    for(i=1; i<=m; i++)
        in>>x[i].x>>x[i].y>>x[i].z;
    sort(x+1, x+m+1, cmp);
    for(i=1; i<=n; i++)
        t[i]=-1;
    for(i=1; i<=m; i++)
    {
        rx=rad(x[i].x);
        ry=rad(x[i].y);
        if(rx!=ry)
        {
            cost+=x[i].z;
            soll[++nrsol].first=x[i].x;
            soll[nrsol].second=x[i].y;
            if(t[rx]<t[ry])
            {
                t[rx]+=t[ry];
                t[ry]=rx;
            }else
            {
                t[ry]+=t[rx];
                t[rx]=ry;
            }
        }
    }
    out<<cost<<"\n"<<nrsol<<"\n";
    for(i=1; i<=nrsol; i++)
        out<<soll[i].first<<" "<<soll[i].second<<"\n";
    return 0;
}