#include <fstream>
#define NMAX 200000
#define MMAX 400000

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie
    {
        int x, y, cost;
        friend bool operator < (Muchie a, Muchie b);
        friend bool operator > (Muchie a, Muchie b);
        friend bool operator <= (Muchie a, Muchie b);
        friend bool operator >= (Muchie a, Muchie b);
    };

bool operator < (Muchie a, Muchie b)
{
    return a.cost < b.cost;
}
bool operator > (Muchie a, Muchie b)
{
    return a.cost > b.cost;
}
bool operator <= (Muchie a, Muchie b)
{
    return a.cost <= b.cost;
}
bool operator >= (Muchie a, Muchie b)
{
    return a.cost >= b.cost;
}
int n, nrsel, m, costotal, cx, cy;
int tata[NMAX], h[NMAX];
Muchie H[MMAX];
Muchie A[NMAX];

void creare();
void combinare(int n, Muchie H[], int poz);
Muchie extrageMin(int &n, Muchie H[]);
int Find(int x); /// returneaza radacina arboreluio din care face parte x
void Union(int x, int y); ///reuneste arborele cu radacina x cu arborele cu radacina y

int main()
{
    int i;
    Muchie mmin;
    creare();
    while (nrsel < n - 1)
    {
        mmin = extrageMin(m, H);//extrag o muchie de cost minim
        cx = Find(mmin.x);
        cy = Find(mmin.y);
        if (cy != cx)
        {
            nrsel++;
            A[nrsel] = mmin;
            costotal += mmin.cost;
            Union(cx, cy);
        }
    }
    fout << costotal << '\n';
    fout << n - 1 << '\n';
    for (i = 1; i < n; i++)
        fout << A[i].x << ' ' << A[i].y << '\n';
    fout.close();
    return 0;
}
void combinare(int n, Muchie H[], int poz)
{
    Muchie x=H[poz];
    int fiu, tata;
 tata=poz;
 fiu=2*tata;
 while (fiu<=n)
       {
         if (fiu+1<=n && H[fiu+1]<H[fiu]) fiu++;
         if (x <= H[fiu]) break;
         H[tata]=H[fiu];
         tata=fiu;
         fiu=2*tata;
        }
  H[tata]=x;
}

void creare()
{int i;
 fin>>n >> m;
 for (i=1; i<=m; i++) fin>>H[i].x >> H[i].y >> H[i].cost;
 for (i=m/2; i>0; i--)
     combinare(m, H, i);
}

Muchie extrageMin(int &n, Muchie H[])
{Muchie minim=H[1];
 H[1]=H[n--];
 combinare(n,H,1);
 return minim;
}
int Find(int x)
/// returneaza radacina arboreluio din care face parte x
{
    int rad, aux;
    rad = x;
    while (tata[rad]) rad = tata[rad]; ///cat timp nodul are nod parinte urc
    ///compresia drumului
    while (tata[x])
    {
        aux = tata[x];
        tata[x] = rad;
        x = aux;
    }
    return rad;
}
void Union(int x, int y)
 ///reuneste arborele cu radacina x cu arborele cu radacina y
 {
     if (h[x] < h[y]) tata[x] = y;
     else
     {
         tata[y] = x;
         if (h[x] == h[y]) h[x]++;
     }
     ///O(1)
 }