#include <cstdio>
#include <vector>
#include <algorithm>

#define NMAX 200007
#define inf 2000000007
#define inf2 2000000009
#define pb push_back
#define DIM 10007

using namespace std;
FILE *fin, *fout;
int n, m, x, arb[3*NMAX], sze, aux = 1, ans[NMAX], sum, poz;
char buff[DIM];
struct arc
{
    int vec;
    int cost;
} tmp, dij[NMAX];
vector<arc> adj[NMAX];

void citeste(int &numar)
{
    numar = 0;
    char semn;
    while(buff[poz] < '0' || buff[poz] > '9')
    {
        semn = buff[poz];
        poz++;
        if(poz == DIM)
        {
            poz = 0;
            fread(buff, 1, DIM, stdin);
        }
    }
    while(buff[poz] >= '0' && buff[poz] <= '9')
    {
        numar = numar * 10 + buff[poz] - '0';
        poz++;
        if(poz == DIM)
        {
            poz = 0;
            fread(buff, 1, DIM, stdin);
        }
    }
    if(semn == '-') numar = -numar;
}

void update(int st, int dr, int pos, int nod)
{
    if(st == dr)
    {
        arb[nod] = pos;
        return ;
    }
    int mij = (st+dr)/2;
    if(pos <= mij) update(st, mij, pos, 2*nod);
    if(pos > mij) update(mij+1, dr, pos, 2*nod+1);
    arb[nod] = (dij[arb[2*nod]].cost < dij[arb[2*nod+1]].cost) ? arb[2*nod] : arb[2*nod+1];
    return ;
}

void citire()
{
    citeste(n);
    citeste(m);
    for(int i = 1; i<= m; ++i)
    {
        citeste(x);
        citeste(tmp.vec);
        citeste(tmp.cost);
        adj[x].pb(tmp);
        swap(x, tmp.vec);
        adj[x].pb(tmp);
    }
}
void init()
{
    for(int i = 1; i<= n; ++i)
    {
        dij[i].cost = inf;
        update(1, n, i, 1);
    }
    dij[1].cost = 0;
}
void prim()
{
    for(int i = 1; i<= n; ++i)
    {
        sze = adj[aux].size();
        for(int j = 0; j< sze; ++j)
        {
            if(dij[adj[aux][j].vec].cost == inf2) continue;
            if(adj[aux][j].cost < dij[adj[aux][j].vec].cost)
            {
                dij[adj[aux][j].vec].cost = adj[aux][j].cost;
                dij[adj[aux][j].vec].vec = aux;
            }
            update(1, n, adj[aux][j].vec, 1);
        }
        ans[aux] = dij[aux].vec;
        sum += dij[aux].cost;
        dij[aux].cost = inf2;
        update(1, n, aux, 1);
        aux = arb[1];
    }
}
void afisare()
{
    printf("%d\n", sum);
    printf("%d\n", n-1);
    for(int i = 2; i<= n; ++i)
    {
        printf("%d %d\n", i, ans[i]);
    }
}
int main()
{
    fin = freopen("apm.in", "r", stdin);
    fout = freopen("apm.out", "w", stdout);
    citire();
    init();
    prim();
    afisare();
    fclose(fin);
    fclose(fout);
    return 0;
}