#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200003
#define MMAX 400003
using namespace std;

struct muchie
{   int x, y, c;
} a[MMAX];

int t[NMAX], nr[NMAX], n, m;
long long cost;
vector<muchie> sol;

ifstream f("apm.in");
ofstream g("apm.out");

inline bool cmp(const muchie &a, const muchie &b)
{   return a.c<b.c;
}

int Rad(int x)
{   int y, k=x;
    while (t[k])
        k=t[k];
    while (t[x])
    {   y=t[x];
        t[x]=k;
        x=y;
    }
    return k;
}

void Unesc(int x, int y)
{   if (nr[x]>nr[y])
    {   t[y]=x;
        nr[x]+=nr[y];
        nr[y]=nr[x];
    }
    else
    {   t[x]=y;
        nr[y]+=nr[x];
        nr[x]=nr[y];
    }
}

int main()
{   int i, num;
    f>>n>>m;
    for (i=1; i<=m; ++i)
    {   f>>a[i].x>>a[i].y>>a[i].c;
        nr[i]=1;
    }
    sort(a+1, a+m+1, cmp);
    num=0;
    for (i=1; i<=m && num<=n-1; ++i)
    {   int rx, ry;
        rx=Rad(a[i].x);
        ry=Rad(a[i].y);
        if (!rx || !ry || rx!=ry)
        {   Unesc(a[i].x, a[i].y);
            cost+=a[i].c;
            num++;
            muchie p;
            p.x=a[i].x;
            p.y=a[i].y;
            sol.push_back(p);
        }
    }
    for (; a[i].c<0 && i<=m; ++i)
    {   int rx, ry;
        rx=Rad(a[i].x);
        ry=Rad(a[i].y);
        if (!rx || !ry || rx!=ry)
        {   Unesc(a[i].x, a[i].y);
            cost+=a[i].c;
            num++;
            muchie p;
            p.x=a[i].x;
            p.y=a[i].y;
            sol.push_back(p);
        }
    }
    g<<cost<<'\n'<<num<<'\n';
    for (i=0; i<n-1; ++i)
        g<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}