#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
pair<int, pair<int,int> > elem;
priority_queue<pair<int,pair<int,int> >, vector<pair<int,pair<int,int> > >, greater<pair<int,pair<int,int> > > > q;
queue< pair<int,int> > p;
pair<int,int> elem2;
vector<pair<int,int> > v;
int n, m, t[200005], cost, nrm, viz[200005], aux;
void citire ()
{
    int x, y, co;
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>x>>y>>co;
        elem.first=co;
        elem.second.first=x;
        elem.second.second=y;
        if (elem.first<0)
        {
            aux=elem.second.first;
            elem.second.first=elem.second.second;
            elem.second.second=aux;
        }
        q.push(elem);
    }
}
int main ()
{
    citire();
    int i;
    nrm=0; i=1;
    viz[1]=1;
    t[1]=0;
    while (nrm<n-1 && i<=m)
    {
        elem=q.top();
        q.pop();
        if (viz[elem.second.first]==0)
        {
            cost+=elem.first;
            nrm++;
            t[elem.second.first]=elem.second.second;
            viz[elem.second.first]=1;
            elem2.first=elem.second.first;
            elem2.second=elem.second.second;
            p.push(elem2);
            v.push_back(elem2);
        }
        else if (viz[elem.second.second]==0)
        {
            t[elem.second.second]=elem.second.first;
            viz[elem.second.second]=1;
            int ok=0;
            for (int j=0; j<v.size() && ok==0; j++)
            {
                elem2=v[i];
                if (elem2.first==elem.second.first && elem2.second==elem.second.second)
                    ok=1;
            }
            if (ok==0)
            {
                cost+=elem.first;
                nrm++;
                elem2.first=elem.second.first;
                elem2.second=elem.second.second;
                p.push(elem2);
            }
        }
        i++;
    }
    fout<<cost<<'\n'<<nrm<<'\n';
    for (i=1; i<=nrm; i++)
    {
        elem2=p.front();
        p.pop();
        fout<<elem2.first<<' '<<elem2.second<<'\n';
    }
}