#include<fstream>
#include<vector>

using namespace std;

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

struct nod{
    int vec,l;
};

const int NMAX = 200001;
const int INF = 1001;

int h[NMAX], pred[NMAX], poz[NMAX], d[NMAX], nh;
vector <nod> v[NMAX];
bool ok[NMAX];

int n,m;

void schimba(int x, int y);
void adauga(int x);
void urca(int p);
void sterge(int p);
void coboara(int p);

void schimba(int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;

    poz[h[x]] = x;
    poz[h[y]] = y;
}

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

void urca(int p)
{
    while(p >= 2 && d[h[p/2]] > d[h[p]])
    {
        schimba(p,p/2);
        p = p/2;
    }
}

void sterge(int p)
{
    schimba(p,nh);
    nh--;
    coboara(p);
}

void coboara(int p)
{
    int f1 = 2*p, f2 = 2*p + 1, bun = p;
    if(f1 <= nh && d[h[bun]] > d[h[f1]]) bun = f1;
    if(f2 <= nh && d[h[bun]] > d[h[f2]]) bun = f2;

    if(bun != p)
    {
        schimba(p,bun);
        coboara(bun);
    }
}

void apm (int p)
{
    int x,nd,dist;
    for(int i = 1; i <= n; i++)
        d[i] = INF;

    adauga(p);
    d[p] = 0;

    while(nh != 0)
    {
        x = h[1];
        sterge(1);
        ok[x] = true;

        for(int i = 0; i < v[x].size(); i++)
        {
            nd = v[x][i].vec;
            dist = v[x][i].l;
            if(!ok[nd] && dist < d[nd])
            {
                d[nd] = dist;
                pred[nd] = x;

                if(poz[nd] == 0)
                    adauga(nd);
                else urca(poz[nd]);
            }
        }
    }
}

void citire()
{
    int x,y,c;

    f >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;
        v[x].push_back((nod){y,c});
        v[y].push_back((nod){x,c});
    }
}

int main()
{
    citire();
    apm(1);

    int s = 0;
    for(int i = 1; i<=n; i++)
        s += d[i];

    g << s << '\n' << n-1 << '\n';

    for(int i = 2; i <= n; i++)
        g << pred[i] << ' ' << i << '\n';
    return 0;
}