#include<cstdio>
#include<algorithm>
using namespace std;
FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

pair<int, int > PerechFinale[400001];
int nrPerechi;

int N,M,CostTotal,tata[200001],rang[200001];
struct Muchie{
    int x,y,cost;
}Muchii[400001];
bool Compare(Muchie a ,Muchie b)
{
    return a.cost<b.cost;
}
void Citire()
{
    fscanf(f,"%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int a1,a2,cost;
        fscanf(f,"%d%d%d",&a1,&a2,&cost);
        Muchii[i].x=a1;
        Muchii[i].y=a2;
        Muchii[i].cost=cost;
    }
    sort(Muchii+1,Muchii+M+1,Compare);

    for(int i=1;i<=N;i++)
    {
         tata[i]=i;
         rang[i]=1;
    }
}
int Find(int nodStart)
{
   while(tata[nodStart]!=nodStart)
        nodStart=tata[nodStart];
  // de exemplu daca tata lui 1 e 3
  // 3 poate sa isi schimbe si el tata pe 7
  // si atunci tatal mare este 7 si pentru 1 si pentru 3
  // si de aia te bagi in while


   return nodStart;
}
void Unire(int x, int y)
{
  if(rang[x]<rang[y])
    tata[x]=y;
  else if(rang[x]>rang[y])
    tata[y]=x;
  else{
    tata[x]=y;
    rang[y]++;
  }
}
void Rezolva()
{
    for(int i=1;i<=M;i++)
    {
        int tatalX=Find(Muchii[i].x);
        int tatalY=Find(Muchii[i].y);
        if(tatalX!=tatalY)
        {
            Unire(tatalX,tatalY);
            PerechFinale[++nrPerechi].first=Muchii[i].x;
            PerechFinale[nrPerechi].second=Muchii[i].y;
            CostTotal+=Muchii[i].cost;
        }
    }
}
void Afisare()
{
    fprintf(g,"%d\n%d\n",CostTotal,nrPerechi);
    for(int i =1;i<=nrPerechi;i++)
        fprintf(g,"%d %d\n",PerechFinale[i].first,PerechFinale[i].second);
}
int main()
{
    Citire();
    Rezolva();
    Afisare();
    fclose(f);
    fclose(g);
    return 0;
}