#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct noduri{int from,to,cost;};
vector<noduri>v,sol;

vector<int>c;
int n,m,s,Nrcomp,Msel;
bool cmp(noduri &i, noduri &j)
{
    return (i.cost>j.cost);
}

void citire()
{
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    int i;
    Nrcomp=n;
    c.push_back(1);
    for(i=1;i<=n;++i)
      c.push_back(i);
    noduri aux;
    for(i=1;i<=m;++i)
     {
         scanf("%d%d%d",&aux.from,&aux.to,&aux.cost);
         v.push_back(aux);
     }
}
void afisare()
{
	freopen("apm.out","w",stdout);
	int i;
	printf("%d\n%d\n",s,sol.size());
	for(i=0;i<sol.size();++i)
	   printf("%d %d\n",sol[i].from,sol[i].to);
}
int main()
{
	citire();
	make_heap(v.begin(),v.end(),cmp);
	while(Msel<n-1)
	{
        noduri aux;
        int minim,maxim,i;
        aux=v.front();

        pop_heap(v.begin(),v.end(),cmp); v.pop_back();
        if(c[aux.from]!=c[aux.to])
        {
            s=s+aux.cost;
            sol.push_back(aux);
            if(c[aux.from]>c[aux.to])
               {
                   minim=c[aux.to];
                   maxim=c[aux.from];
               }
            else
               {
                   minim=c[aux.from];
                   maxim=c[aux.to];
               }
            replace(c.begin(),c.end(),maxim,minim);
            --Nrcomp;
            ++Msel;
        }
	}
	afisare();
    return 0;
}