#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 200005;
const int INF = 1e9;
const int M = 400005;

int vf[2*M],urm[2*M],lst[2*M],cst[2*M],n,m,nr,heap[N],h,poz[N],dist[N],viz[N],daddy[N],cost,muchii;

void Adauga_graf(int x,int y,int z)
{
    vf[++nr] = y;
    cst[nr] = z;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void Schimb(int p,int q)
{
    swap(heap[p], heap[q]);
    poz[heap[p]] = p;
    poz[heap[q]] = q;
}

void Urca(int p)
{
    while (p > 1 && dist[heap[p]] < dist[heap[p/2]])
    {
        Schimb(p, p/2);
        p /= 2;
    }
}

void Coboara(int p)
{
    int fs = 2*p, fd= 2*p+1, bun = p;
    if (fs <= h && dist[heap[fs]] < dist[heap[bun]])
    {
        bun = fs;
    }
    if (fd <= h && dist[heap[fd]] < dist[heap[bun]])
    {
        bun = fd;
    }
    if (bun != p)
    {
        Schimb(p, bun);
        Coboara(bun);
    }
}

void Adauga(int nr)
{
    heap[++h] = nr;
    poz[nr] = h;
    Urca(h);
}

void Sterge()
{
    Schimb(1 , h--);
    Coboara(1);
}

void Prim()
{
    for (int i=2; i<=n; i++)
    {
        dist[i] = INF;
    }
    for (int i=1; i<=n; i++)
    {
        Adauga(i);
    }
    while (h > 0)
    {
        int x = heap[1];
        cost += dist[x];
        Sterge();
        muchii++;
        poz[x] = -1;
        for (int p=lst[x]; p!=0; p=urm[p])
        {
            int y = vf[p];
            int c = cst[p];
            if (poz[y] != -1 && c < dist[y])
            {
                dist[y] = c;
                Urca(poz[y]);
                daddy[y] = x;
            }
        }
    }
}

int main()
{
    in >> n >> m;
    for (int i=1,x,y,z; i<=m; i++)
    {
        in >> x >> y >> z;
        Adauga_graf(x,y,z);
        Adauga_graf(y,x,z);
    }
    Prim();
    out << cost << "\n";
    out << muchii << "\n";
    for (int i=2; i<=n; i++)
    {
        out << daddy[i] << " " << i << "\n";
    }
    return 0;
}