#include <cstdio>

using namespace std;

FILE *in, *out;

const int MAX_N = 100000, MAX_M = 400000;

int lst[MAX_N+1], urm[2*MAX_M+1], vf[2*MAX_M+1], c[2*MAX_M+1];
int nrg;

void add(int x, int y, int z)
{
    nrg++;
    vf[nrg] = y;
    c[nrg] = z;
    urm[nrg] = lst[x];
    lst[x] = nrg;
}

int n, m;
//int x[MAX_M], y[MAX_M], c[MAX_M];

int apm[MAX_N];
int nr;

bool inAPM[MAX_N+1];

int h[MAX_M+1];
int nh;

void change(int p1, int p2)
{
    h[p1] = h[p1]^h[p2];
    h[p2] = h[p1]^h[p2];
    h[p1] = h[p1]^h[p2];
}

void urca(int p)
{
    while(p != 1 && c[h[p]] < c[h[p/2]])
    {
        change(p, p/2);
        p /= 2;
    }
}

void coboara(int p)
{
    int fs = 2*p, fd = fs+1, bun = p;
    if(fs <= nh && c[h[bun]] > c[h[fs]])
        bun = fs;
    if(fd <= nh && c[h[bun]] > c[h[fd]])
        bun = fd;
    if(bun != p)
    {
        change(bun, p);
        coboara(bun);
    }
}

void push(int x)
{
    h[++nh] = x;
    urca(nh);
}

int pop()
{
    int rez = h[1];
    change(1, nh--);
    coboara(1);
    return rez;
}

int pereche(int p)
{
    p = (p&1)?(p+1):(p-1);
    return vf[p];
}

int main()
{
    in= fopen("apm.in", "r");
    out = fopen("apm.out", "w");
    fscanf(in, "%d%d", &n, &m);
    int x, y, z;
    for(int i = 0; i < m; i++)
    {
        fscanf(in, "%d%d%d", &x,&y,&z);
        add(x, y, z);
        if(x == 1) push(nrg);
        add(y, x, z);
        if(y == 1) push(nrg);
    }
    inAPM[1] = true;
    int p;
    int cost = 0;
    for(int i = 1; i < n; i++)
    {
        p = pop();
        x = vf[p];
        y = pereche(p);
        if(!inAPM[x] || !inAPM[y])
        {
            apm[nr++] = p;
            cost += c[p];
            if(!inAPM[x])
            {
                int poz = lst[x];
                while(poz != 0)
                {
                    if(!inAPM[vf[poz]])
                        push(poz);
                    poz = urm[poz];
                }
            } else
                if(!inAPM[y])
                {
                    int poz = lst[y];
                    while(poz != 0)
                    {
                        if(!inAPM[vf[poz]])
                            push(poz);
                        poz = urm[poz];
                    }
                }
            inAPM[x] = inAPM[y] = true;
        } else i--;
    }
    fprintf(out, "%d\n%d\n", cost, nr);
    for(int i = 0; i < nr; i++)
    {
        x = vf[apm[i]];
        y = pereche(apm[i]);
        fprintf(out, "%d %d\n", x, y);
    }
    fcloseall();
    return 0;
}