#include <fstream>
#define NMAX 200002
#define MMAX 400002
using namespace std;

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

int T[NMAX], H[NMAX];

void Union(int x, int y);
int Find(int x);

typedef struct
{
  int x, y, cost;
} muchie;
muchie G[MMAX];
struct
{
    int x, y;
} solutie[MMAX];

void inserare(muchie H[], int &n, muchie x);
void combinare(muchie H[], int n, int i);
muchie extragere(muchie H[], int &n);

int sum;
int n, m;

int main(void)
{
    int i;
    fin>>n>>m;
    for (i = 1; i <= m; ++i)
    {
        fin>>G[i].x>>G[i].y>>G[i].cost;
    }

    for (i = m/2; i >= 1; --i) combinare(G, m, i);

    int rx, ry;
    muchie a;
    n = 0;
    while (m > 0)
    {
        a = extragere(G, m);
        rx = Find(a.x);
        ry = Find(a.y);
        if (rx != ry)
        {
            sum += a.cost;

            ++n;
            solutie[n].x = a.x;
            solutie[n].y = a.y;

            Union(rx, ry);
        }
    }

    fout<<sum<<'\n';
    fout<<n<<'\n';
    for (i = 1; i <= n; ++i) fout<<solutie[i].y<<' '<<solutie[i].x<<'\n';

    return 0;
}


muchie extragere(muchie H[], int &n)
{
    muchie x = H[1];
    H[1] = H[n];
    n--;
    combinare(H, n, 1);
    return x;
}

void combinare(muchie H[], int n, int i)
{
    muchie x = H[i];
    int tata = i, fiu = 2 * tata;
    while (fiu <= n)
    {
        if (fiu+1 <= n && H[fiu].cost > H[fiu+1].cost) ++fiu;
        if (x.cost > H[fiu].cost)
        {
            H[tata] = H[fiu];
            tata = fiu;
            fiu = 2 * tata;
        }
        else break;
    }

    H[tata] = x;
}

void inserare(muchie H[], int &n, muchie x)
{
    int fiu = n+1, tata = fiu / 2;
    while (tata && H[tata].cost > x.cost)
    {
        H[fiu] = H[tata];
        fiu = tata;
        tata = fiu / 2;
    }

    H[fiu] = x;
    ++n;
}

void Union( int x, int y)
{
    if(H[x]<H[y])
    {
        T[x]=y;
    }
    else if(H[x]>H[y])
    {
        T[y]=x;
    }
    else
    {
        T[y]=x;
        H[x]++;
    }

}
int Find(int x)
{
    int r,y;
    //mai intai aflu rad arborelui din care face parte x
    r=x;
    while(T[r]) r=T[r];
    //parcurg din nou drumul de la x la r si fac toate nod fii a lui r

    return r;
}
/*int Find1(int x) {
  if (T[x] == 0) return x;
  T[x] = Find(T[x]);
  return T[x];
}*/