#include <fstream>

#define MAX 100000

using namespace std;

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

int s,minn,k,n,sf;
int t[200001];
int vize[200001];
bool viz[200001];

struct Nod
{
    int inf;
    int c;
    Nod *urm;
};

typedef Nod *PNod;

PNod L[200001];

void ad(PNod &vf, int x, int co)
{
    PNod p = new Nod;
    p -> inf = x;
    p -> c = co;
    p -> urm = vf;
    vf = p;
}

int cata()
{
    int tata = 0,nod;
    for(int i = 1; i <= sf; i++)
        for(PNod p = L[vize[i]]; p; p = p -> urm)
            if(!viz[p -> inf] && p -> c < minn)
            {
                tata = vize[i];
                nod = p -> inf;
                minn = p -> c;
            }
    vize[++sf] = nod;
    viz[nod] = true;
    t[nod] = tata;
    return minn;
}

void prim()
{
    while(sf < n)
    {
        minn = MAX;
        cata();
        s += minn;
    }

    g << s << "\n" << n - 1 << "\n";
    for(int i = 2; i <= n; i++) g << i << " " << t[i] << "\n";
}

int main()
{
    int m,x,y,c;

    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        ad(L[x],y,c);
        ad(L[y],x,c);
    }

    viz[1] = true;
    vize[++sf] = 1;
    prim();
    return 0;
}