#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 200003
#define MMAX 400003
FILE *fin,*fout;
using namespace std;
//ifstream fin("flood.in");
//ofstream fout("flood.out");
struct muchie {int x,y,cost; bool ok;};
struct solutie{int x,y;};
solutie sol[NMAX];
vector <muchie> Muchie;
void citire();
void apm();
int n,m,Tata[NMAX],H[NMAX],drumuri,ctotal;
bool comp(muchie a, muchie b)
{
    return a.cost>b.cost||(a.cost==b.cost &&a.x>b.x);
}
int main()
{
    int i;
    citire();
    make_heap(Muchie.begin(),Muchie.end(),comp);
    apm();
}
void citire()
{
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    int a,b,c,i;
    muchie aux;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&a,&b,&c);
        aux.x=a;aux.y=b;aux.cost=c;aux.ok=0;
        Muchie.push_back(aux);
    }

}
void Union(int i, int j)
{
    if(H[i]<H[j]) Tata[i]=j;
    else
        if(H[i]>H[j]) Tata[j]=i;
            else {Tata[j]=i;H[i]++;}
}
int Find(int care)
{
    int aux,rad;
    rad=care;
    while(Tata[rad]!=0) rad=Tata[rad];
    // compresia drumului
    while(care!=rad) {H[care]=0; aux=Tata[care]; Tata[care]=rad; care=aux; }
    return rad;
}

void apm()
{
    int k,cx,cy,i;
    int poz=1;
    muchie vf;
    while(!Muchie.empty())
    {
        vf=Muchie.front();
        pop_heap(Muchie.begin(),Muchie.end(),comp);
        Muchie.pop_back();
        cx=Find(vf.x);
        cy=Find(vf.y);
        if(cx!=cy)
        {
            drumuri++;
            ctotal+=vf.cost;
            sol[drumuri].x=vf.x;
            sol[drumuri].y=vf.y;
            k++;
            Union(cx,cy);
         }
       poz++;
    }
    fprintf(fout,"%d\n%d\n",ctotal,drumuri);
    for(i=1;i<=drumuri;i++) fprintf(fout,"%d %d\n",sol[i].y,sol[i].x);
}