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

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

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

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()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; ++i)
    {
        scanf("%d %d %d", &x, &tmp.vec, &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;
}