#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
typedef struct{unsigned int u,v;
                int c;} muchie;
unsigned int v,u,n,m,i,j;
long S; //costul arborelui
unsigned int r[200000];
vector <muchie> e;
vector <muchie> A; //arborele partial de cost min
muchie x;

void quickSort(int left, int right) {
      int i=left, j=right;
      muchie tmp;
      muchie pivot=e[(left + right)/2];
      /* partition */
      while (i <= j) {
            while (e[i].c<pivot.c)
                  i++;
            while (e[j].c>pivot.c)
                  j--;
            if (i <= j) {
                  tmp=e[i];
                  e[i]=e[j];
                  e[j]=tmp;
                  i++;
                  j--;
            }
      };
      /* recursion */
      if (left < j)
            quickSort(left, j);
      if (i < right)
            quickSort(i, right);
}

int main()
{
    f>>n>>m;
    int aux,k;
    for (i=0; i<m; i++) //citire
    {
        f>>x.u>>x.v>>x.c;
        e.push_back(x);
    }
    for (i=1; i<=n; i++)
        r[i]=i; //initial fiecare varf este un arbore
    quickSort(0,e.size()-1); //sorteaza muchiile crescator
    for (i=0; i<e.size(); i++)
        if (e[i].u>e[i].v)
        {
            aux=e[i].u;
            e[i].u=e[i].v;
            e[i].v=aux;
        }
    for (i=0; i<e.size(); i++)
        if (r[e[i].u]!=r[e[i].v])
        {
            k=r[e[i].v];
            A.push_back(e[i]);
            S+=e[i].c;
            //Union (u,v) -- schimbam reprezentatii
            for (j=1; j<=n; j++)
                if (r[j]==k)
                    r[j]=r[e[i].u];
            if (A.size()==n-1)
                break;
        }
    g<<S<<'\n';
    g<<n-1<<'\n';
    for (i=0; i<A.size(); i++)
        g<<A[i].u<<" "<<A[i].v<<" "<<'\n';
    return 0;
}