#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

const int NMAX = 200001;
const int INF = 1 << 30;
struct nod
{
    int x, cost;
};

struct raspuns
{
    int start, stop, cost;
};

struct compara
{
    bool operator () (nod a, nod b) {
        return a.cost > b.cost;
    }
};

int Suma_Totala = 0;
int N, M;
int dist[NMAX];
int tata[NMAX];
int viz[NMAX];
std::priority_queue <nod,std::vector<nod>, compara > Q;
std::vector<std::pair<int, int>>G[NMAX];
std::vector<raspuns> Rez;

void Citire()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        G[x].push_back({ y,cost });
        G[y].push_back({ x,cost });
    }
}

void Initializare()
{
    for (int i = 1; i <= N; ++i)
    {
        dist[i] = INF;
        tata[i] = 0;
       
    }
    dist[1] = 0;
    nod a;
    a.x = 1;
    a.cost = 0;
    Q.push(a);

}

void test_coada()
{
    while (!Q.empty())
    {
        std::cout << Q.top().x << " " << Q.top().cost << '\n';
        Q.pop();
    }
}

void Prim()
{
    int nr_varfuri = N-1;
    /* //Implementare M log N
    while (nr_varfuri)
    {
        while (viz[Q.top().x])
            Q.pop();
        nod nod_ieftin = Q.top();
        Q.pop();
        viz[nod_ieftin.x] = 1;
        if (tata[nod_ieftin.x] != 0)
        {
            raspuns r;
            r.start = tata[nod_ieftin.x];
            r.stop = nod_ieftin.x;
            r.cost = nod_ieftin.cost;
            Rez.push_back(r);
            nr_varfuri--;
            Suma_Totala += nod_ieftin.cost;
        }
        for (auto vecin : G[nod_ieftin.x])
        {
            if (viz[vecin.first] == 0) 
            {
                if (dist[vecin.first] > vecin.second)
                {
                    dist[vecin.first] = vecin.second;
                    tata[vecin.first] = nod_ieftin.x;
                    nod nou;
                    nou.x = vecin.first;
                    nou.cost = vecin.second;
                    Q.push(nou);

                }
            }
        }
    }

    */
    nr_varfuri++;
    while (nr_varfuri)
    {
        int distanta_minima = INF;
        int varf_min_tura = 0;
        for (int i = 1; i <= N; ++i)
        {
            if (viz[i] == 0)
            {
                if (dist[i] < distanta_minima)
                {
                    varf_min_tura = i;
                    distanta_minima = dist[i];
                }
            }
        }
        viz[varf_min_tura] = 1;
        Suma_Totala += distanta_minima;
        for (auto vecin : G[varf_min_tura])
        {
            if (dist[vecin.first] > vecin.second)
            {
                dist[vecin.first] = vecin.second;
                if(tata[vecin.first] == 0)
                tata[vecin.first] = varf_min_tura;
            }
        }
        nr_varfuri--;
    }

}

void Afisare()
{

    /*
    fout << Suma_Totala << '\n';
    fout << N - 1 << '\n';
    for (auto raspuns : Rez)
    {
        fout << raspuns.start << " " << raspuns.stop << '\n';
    }
    */
    fout << Suma_Totala << '\n';
    fout << N - 1 << '\n';
    for (int i = 2; i <= N; ++i)
    {
        fout << i << " " << tata[i] << '\n';
    }
}


int main()
{
    Citire();
    Initializare();
    //test_coada();
    Prim();
    Afisare();
}