#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct muchie {int x, y, c, marc;}aux;
int t[105], n, k, cost, nrm, aux2;
vector<muchie> v;
void citire ()
{
    fin>>n>>k;
    for (int i=1; i<=k; i++)
    {
       fin>>aux.x>>aux.y>>aux.c;
       if (aux.c<0)
       {
           //aux.c*=-1;
           aux2=aux.x;
           aux.x=aux.y;
           aux.y=aux2;
       }
       v.push_back(aux);
    }

}
bool cmp (muchie a, muchie b)
{
    if (a.c<b.c)return true;
    return false;
}
int main ()
{
    int i, j, t1, t2;
    citire();
    for (i=1; i<=n; i++) t[i]=i;
    sort(v.begin(), v.end(), cmp);
    nrm=0;
    i=0;
    while (nrm<n-1 && i<k)
    {
        if (t[v[i].x]!=t[v[i].y])
        {
            nrm++;
            cost+=v[i].c;
            v[i].marc=1;
            t1=t[v[i].x];
            t2=t[v[i].y];
            for (j=1; j<=n; j++)
                if (t[j]==t2)t[j]=t1;
        }
        i++;
    }
    fout<<cost<<'\n';
    fout<<nrm<<'\n';
    for (i=0; i<v.size(); i++)
       if (v[i].marc==1) fout<<v[i].x<<' '<<v[i].y<<'\n';

    fin.close();
    fout.close();
    return 0;
}