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