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

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

void Sort()
{
    for (i=0; i<m-1; i++)
        for (j=i; j<m; j++)
            if (e[i].c>e[j].c)
            {
                x=e[i];
                e[i]=e[j];
                e[j]=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;
    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 (r[e[i].u]!=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]==r[e[i].u])
                    r[j]=r[e[i].v];
            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;
}