#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

class muchie{
    public:
int nod1;
int nod2;
int cost;

muchie(){
nod1=0;nod2=0;cost=0;
}
muchie(int,int,int);

void operator=(const muchie &d);
void operator=(int);
bool operator>(const muchie &d);
bool operator==(const muchie &d);

};

vector<muchie> cost;
int a,n,m,i,viz[10];

bool muchie::operator==(const muchie &d){
    if(nod1==d.nod1&&nod2==d.nod2&&cost==d.cost)
        return true;
        return false;
}

bool muchie::operator>(const muchie &d){
if(cost>d.cost)
    return true;
return false;

}

void muchie::operator=(int a){
nod1=0;
nod2=0;
cost=0;
}

muchie::muchie(int a, int b, int c)
{
    nod1=a;
    nod2=b;
    cost=c;
}

void muchie::operator=(const muchie &d){
nod1=d.nod1;
nod2=d.nod2;
cost=d.cost;
}

void sortare(int a){
    for(int i=0;i<a;i++)
         for(int j=i+1;j<a;j++)
            if(cost[i]>cost[j])
                {
                muchie aux;
                aux=cost[i];
                cost[i]=cost[j];
                cost[j]=aux;
                }

}



int main()
{
    f>>m;
	f>>n;

	int a,b,c;

	for(i=1;i<=n;i++)
	{
        f>>a>>b>>c;
        muchie m(a,b,c);
        cost.push_back(m);
	}

	sortare(n);

	for(i=0;i<cost.size();i++)
    {
        if(viz[cost[i].nod1]==0 || viz[cost[i].nod2]==0)
        {
            viz[cost[i].nod1]=1;
            viz[cost[i].nod2]=1;
        }
        else
        {
            cost[i]=0;
        }
    }

    int nrNoduri=0;
    int costtotal=0;
    for(i=0;i<cost.size();i++)
    {
        if(cost[i].cost!=0)
        {nrNoduri++;
        costtotal+=cost[i].cost;
        }
    }
        g<<costtotal<<endl;
        g<<nrNoduri<<endl;

    for(i=0;i<cost.size();i++)
    {
        if(cost[i].cost!=0)
        {g<<cost[i].nod1<<" "<<cost[i].nod2<<endl;
        costtotal+=cost[i].cost;
        }
    }



}