#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 400001;

int N, M, COST;
int t[NMAX], rang[NMAX];

struct muchie
{
    int x, y, cost;
}; muchie m[NMAX];

bool compara(const muchie &m1, const muchie &m2)
{
    return m1.cost < m2.cost;
}

void citire()
{
    ifstream in ("apm.in");
    in >> N >> M;
    for (int i = 1; i <= M; ++i)
        in >> m[i].x >> m[i].y >> m[i].cost;
    in.close();
}

int tataNod(int nod) //cautarea se opreste cand tatal lui x e x
{
    while(t[nod] != nod)
        nod = t[nod];
    return nod;
}

void unire(int x, int y)
{
    if(rang[x] < rang[y])
        t[x] = y;
    if(rang[y] < rang[x])
        t[y] = x;
    if(rang[x] == rang[y])
    {
        t[x] = y;
        rang[y]++;
    }
}

void kruskal(int n)  //multimi disjuncte
{
   COST = 0;
   sort(m + 1, m + M + 1, compara);

   for(int i = 1; i <= n; ++i)
    rang[i] = 1;

   for(int i = 1; i <= n; ++i)
   {
       int rangg1 = tataNod(m[i].x);
       int rangg2 = tataNod(m[i].y);

       if(rangg1 != rangg2)
       {
           t[n] = i;
           COST = m[i].cost + COST;
           unire(rangg1, rangg2);
           n--;
       }
   }

}

void afisare()
{
    ofstream out ("apm.out");
    out << COST << '\n' << N-1 << '\n';

    for(int i = 1; i <= N; ++i)
        out << m[t[i]].x << ' ' << m[t[i]].y << '\n';
    out.close();
}

int main()
{
    citire();
    kruskal(N);
    afisare();
    return 0;
}