#include <fstream>
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN = 200005;

ifstream fin("apm.in");
ofstream fout("apm.out");

int N, M;
int D[MAXN], T[MAXN];
int costAPM, nr_muchii;
bool Used[MAXN];

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

Nod *G[MAXN];

void Prim()
{
    int vmin, p;
    Nod *q;
    for (int i = 2; i <= N; ++i)
    {
        D[i] = INF;
        T[i] = -1;
    }
    for (int k = 1; k <= N; ++k)
    {
        vmin = INF;
        for (int i = 1; i <= N; ++i)
        {
            if (!Used[i] && D[i] < vmin)
            {
                vmin = D[i];
                p = i;
            }
        }
        costAPM += D[p];
        Used[p] = 1;
        for (q = G[p]; q != 0; q = q -> urm)
        {
            int vecin = q -> v;
            int cost = q -> c;
            if (!Used[vecin] && D[vecin] > cost)
            {
                D[vecin] = cost;
                T[vecin] = p;
            }
        }
    }
}

void WriteData()
{
    fout << costAPM << '\n';
    fout << N - 1 << '\n';
    for (int i = 2; i <= N; ++i)
        fout << i << " " << T[i] << '\n';

}

void ReadData()
{
    Nod *p;
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        p = new Nod;
        p -> v = y;
        p -> c = cost;
        p -> urm = G[x];
        G[x] = p;

        p = new Nod;
        p -> v = x;
        p -> c = cost;
        p -> urm = G[y];
        G[y] = p;
    }
}

int main()
{
    ReadData();
    Prim();
    WriteData();
    fin.close();
    fout.close();
    return 0;
}